import os
from random import randrange, sample
from math import ceil
import time
try:
    from .SM3 import digest as sm3
except:
    from SM3 import digest as sm3
from collections import namedtuple
# import multiprocessing
# from concurrent.futures import ThreadPoolExecutor


# SM9总则(GB_T 38635.1-2020) A.1 系统参数
q = 0XB640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D  # 基域特征
N = 0XB640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25  # 群的阶
# 群G1的生成元 P1=(x_p1, y_p1)
x_p1 = 0X93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD
y_p1 = 0X21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616
# 群G2的生成元 P2=(x_p2, y_p2)
x_p2 = (0X85AEF3D078640C98597B6027B441A01FF1DD2C190F5E93C454806C11D8806141,
        0X3722755292130B08D2AAB97FD34EC120EE265948D19C17ABF9B7213BAF82D65B)
y_p2 = (0X17509B092E845C1266BA0D262CBEE6ED0736A96FA347C8BD856DC76B84EBEB96,
        0XA7CF28D519BE3DA65F3170153D278FF247EFBA98A71A08116215BBA5C999A7C7)
HASH_SIZE = 32  # sm3输出256位（32字节）
N_SIZE = 32  # 阶的字节数
KEY_LEN = 128  # 默认密钥位数
K2_len = 256  # MAC函数中密钥K2的位数


def to_byte(x, size=None):
    if type(x) is int:
        return x.to_bytes(size if size else ceil(x.bit_length() / 8), byteorder='big')
    elif type(x) in (str, bytes):
        x = x.encode() if type(x) is str else x
        return x[:size] if size and len(x) > size else x  # 超过指定长度，则截取左侧字符
    elif type(x) in (tuple, list):
        return b''.join(to_byte(c, size) for c in x)
    return bytes(x)[:size] if size else bytes(x)


# 将字节转换为int
def to_int(byte):
    return int.from_bytes(byte, byteorder='big')


# 广义的欧几里得除法求模逆（耗时约为slow/SM2代码内get_inverse函数的43%）
def mod_inv(a, mod=q):
    if a == 0:
        return 0
    lm, low, hm, high = 1, a % mod, 0, mod
    while low > 1:
        r = high // low
        lm, low, hm, high = hm - lm * r, high - low * r, lm, low
    return lm % mod


class FQ:
    def __init__(self, n):
        self.n = n

    def __add__(self, other):
        return FQ(self.n + other.n)

    def __sub__(self, other):
        return FQ(self.n - other.n)

    def __mul__(self, other):  # 右操作数可为int
        return FQ(self.n * (other.n if type(other) is FQ else other) % q)

    def __truediv__(self, other):  # 右操作数可为int
        return FQ(self.n * mod_inv(other.n if type(other) is FQ else other) % q)

    def __pow__(self, other):  # 操作数应为int
        return FQ(pow(self.n, other, q) if other else 1)

    def __eq__(self, other):  # 右操作数可为int
        return self.n % q == (other.n if type(other) is FQ else other) % q

    def __neg__(self):
        return FQ(-self.n)

    def __repr__(self):
        return 'FQ(%064X)' % (self.n % q)

    def __bytes__(self):
        return to_byte(self.n % q, N_SIZE)

    def is_zero(self):
        return self.n % q == 0

    def inv(self):
        return FQ(mod_inv(self.n))

    def sqr(self):
        return FQ(self.n * self.n % q)

    @classmethod
    def one(cls):
        return cls(1)

    @classmethod
    def zero(cls):
        return cls(0)


class FQ2:
    def __init__(self, *coeffs):  # 国标中的表示是高位在前，而此处coeffs是低位在前
        self.coeffs = coeffs

    def __add__(self, other):
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        return FQ2(a0 + b0, a1 + b1)

    def __sub__(self, other):
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        return FQ2(a0 - b0, a1 - b1)

    def __pow__(self, other):
        t = self
        for ri in bin(other)[3:]:
            t = t.sqr() * self if ri == '1' else t.sqr()
        return t

    def sqr(self):
        a0, a1 = self.coeffs
        return FQ2((a0 * a0 - (a1 * a1 << 1)) % q, (a0 * a1 << 1) % q)  # (a0^2 - 2 * a1^2, 2 * a0 * a1)

    def sqr_u(self):
        a0, a1 = self.coeffs
        return FQ2(-(a0 * a1 << 2) % q, (a0 * a0 - (a1 * a1 << 1)) % q)  # (-4 * a0 * a1, a0^2 - 2 * a1^2)

    def mul_b_u(self, b):  # 带参数乘法
        (a0, a1), (b0, b1) = self.coeffs, b.coeffs
        return FQ2(-(a0 * b1 + a1 * b0 << 1) % q, (a0 * b0 - (a1 * b1 << 1)) % q)  # (-2*(a0*b1+a1*b0), a0*b0-2*a1*b1)

    def __mul__(self, other):
        if type(other) is int:
            a0, a1 = self.coeffs
            return FQ2(a0 << 1, a1 << 1) if other == 2 else FQ2(a0 * other % q, a1 * other % q)
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        a0b0, a1b1 = a0 * b0, a1 * b1  # Karatsuba 思想方法（节约一次乘法），实测此处约有5%提升，用在其他地方未见性能提升
        return FQ2((a0b0 - (a1b1 << 1)) % q, ((a0 + a1) * (b0 + b1) - (a0b0 + a1b1)) % q)  # (a0*b0-2*a1*b1,a0*b1+a1*b0)

    def __rmul__(self, other):
        return self.__mul__(other)

    def __truediv__(self, other):
        if type(other) is int:
            other_inv = mod_inv(other)
            return FQ2([c * other_inv % q for c in self.coeffs])
        return self * other.inv()

    def inv(self):
        a0, a1 = self.coeffs
        if a0 == 0:
            return FQ2(0, -mod_inv(a1 << 1))  # (0, -(2 * a1)^-1)
        if a1 == 0:
            return FQ2(mod_inv(a0), 0)  # (a0^-1, 0)
        k = mod_inv(a0 * a0 + (a1 * a1 << 1))  # k = (a0^2 + 2 * a1^2)^-1
        return FQ2(a0 * k % q, -a1 * k % q)  # (a0 * k, -a1 * k)

    def conjugate(self):  # 共轭
        a0, a1 = self.coeffs
        return self.__class__(a0, -a1)

    def get_fp_list(self):  # 返回所有基域元素（高位在前）
        if type(self) is FQ2:
            return [i % q for i in self[::-1]]
        return [y for x in self[::-1] for y in x.get_fp_list()] if self.coeffs else [0] * 4  # 注意FQ4对象零值的处理

    def __repr__(self):
        return '%s(%s)' % (self.__class__.__name__, ', '.join('%064X' % i for i in self.get_fp_list()))

    def __bytes__(self):  # 字节串高位在前
        return to_byte(self.get_fp_list(), N_SIZE)

    def __eq__(self, other):
        return self.get_fp_list() == other.get_fp_list()

    def __neg__(self):
        return self.__class__(*[-c for c in self.coeffs])

    def __getitem__(self, item):
        return self.coeffs[item]

    def is_zero(self):
        return all(c % q == 0 for c in self.coeffs) if type(self) is FQ2 else all(c.is_zero() for c in self.coeffs)

    @classmethod
    def one(cls):
        return FQ2_one if cls is FQ2 else (FQ12_one if cls is FQ12 else FQ4_one)

    @classmethod
    def zero(cls):
        return FQ2_zero if cls is FQ2 else ()


class FQ4(FQ2):  # 零元的coeffs为空，可优化FQ12稀疏乘法运算
    def __add__(self, other):
        if not self.coeffs:
            return other
        if not other.coeffs:
            return self
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        return FQ4(a0 + b0, a1 + b1)

    def __sub__(self, other):
        if not self.coeffs:
            return -other
        if not other.coeffs:
            return self
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        return FQ4(a0 - b0, a1 - b1)

    def sqr(self):
        if not self.coeffs:
            return FQ4_zero
        a0, a1 = self.coeffs
        return FQ4(a0.sqr() + a1.sqr_u(), a0 * a1 * 2)  # (a0^2 + a1^2 * u, 2 * a0 * a1)

    def sqr_v(self):
        if not self.coeffs:
            return FQ4_zero
        a0, a1 = self.coeffs
        return FQ4(a0.mul_b_u(a1) * 2, a0.sqr() + a1.sqr_u())  # (2 * a0 * a1 * u, a0^2 + a1^2 * u)

    def mul_b_v(self, b):  # 带参数乘法
        if not self.coeffs or not b.coeffs:
            return FQ4_zero
        (a0, a1), (b0, b1) = self.coeffs, b.coeffs
        return FQ4(a0.mul_b_u(b1) + a1.mul_b_u(b0), a0 * b0 + a1.mul_b_u(b1))  # (a0*b1*u+a1*b0*u, a0*b0+a1*b1*u)

    def __mul__(self, other):
        if not self.coeffs:
            return FQ4_zero
        if type(other) is int:
            a0, a1 = self.coeffs
            return FQ4(a0 * other, a1 * other)
        if not other.coeffs:
            return FQ4_zero
        (a0, a1), (b0, b1) = self.coeffs, other.coeffs
        return FQ4(a0 * b0 + a1.mul_b_u(b1), a0 * b1 + a1 * b0)  # (a0*b0+a1*b1*u, a0*b1+a1*b0)

    def inv(self):
        if not self.coeffs:
            return FQ4_zero
        a0, a1 = self.coeffs
        k = (a1.sqr_u() - a0.sqr()).inv()
        return FQ4((-a0 * k), a1 * k)


class FQ12(FQ2):
    def __add__(self, other):
        (a0, a1, a2), (b0, b1, b2) = self.coeffs, other.coeffs
        return FQ12(a0 + b0, a1 + b1, a2 + b2)

    def __sub__(self, other):
        (a0, a1, a2), (b0, b1, b2) = self.coeffs, other.coeffs
        return FQ12(a0 - b0, a1 - b1, a2 - b2)

    def sqr(self):
        a0, a1, a2 = self.coeffs
        return FQ12(a0.sqr() + a1.mul_b_v(a2) * 2, a0 * a1 * 2 + a2.sqr_v(), a0 * a2 * 2 + a1.sqr())

    def __mul__(self, other):
        (a0, a1, a2), (b0, b1, b2) = self.coeffs, other.coeffs
        return FQ12(a0 * b0 + a1.mul_b_v(b2) + a2.mul_b_v(b1), a0 * b1 + a1 * b0 + a2.mul_b_v(b2),
                    a0 * b2 + a1 * b1 + a2 * b0)

    def GT_sqr(self):  # 分圆循环子群Gϕ6(FQ2)中的元素平方，Gϕ6(FQ2)简称为GT
        a, b, c = self.coeffs
        a2, b2, c2v = a.sqr(), b.sqr(), c.sqr_v()
        return FQ12(a2 + (a2 - a.conjugate()) * 2, c2v + (c2v + b.conjugate()) * 2, b2 + (b2 - c.conjugate()) * 2)

    def __pow__(self, other):  # 实际运行此函数的对象都是GT中的元素
        if other > 10:  # 加减法
            h, k = bin(3 * other)[2:], bin(other)[2:]
            k, t, nf = '0' * (len(h) - len(k)) + k, self, self.frobenius6()
            for i in range(1, len(h) - 1):
                t = t.GT_sqr()
                if h[i] == '1' and k[i] == '0':
                    t = t * self
                elif h[i] == '0' and k[i] == '1':
                    t = t * nf
        else:
            t = self
            for ri in bin(other)[3:]:
                t = t.GT_sqr() * self if ri == '1' else t.GT_sqr()
        return t

    def inv(self):
        a0, a1, a2 = self.coeffs
        a0_2, a1_2 = a0.sqr(), a1.sqr()
        if a2.is_zero():
            k = (a0 * a0_2 + a1.mul_b_v(a1_2)).inv()
            return FQ12(a0_2 * k, (-a0 * a1 * k), a1_2 * k)
        t0, t1, t2 = a1_2 - a0 * a2, a0 * a1 - a2.sqr_v(), a0_2 - a1.mul_b_v(a2)
        t3 = a2 * (t1.sqr() - t0 * t2).inv()
        return FQ12(t2 * t3, (-t1 * t3), t0 * t3)

    def frobenius(self):
        (a0, a1), (b0, b1), (c0, c1) = self.coeffs
        a = FQ4(a0.conjugate(), a1.conjugate() * alpha3)
        b = FQ4(b0.conjugate() * alpha1, b1.conjugate() * alpha4)
        c = FQ4(c0.conjugate() * alpha2, c1.conjugate() * alpha5)
        return FQ12(a, b, c)

    def frobenius2(self):
        a, b, c = self.coeffs
        return FQ12(a.conjugate(), b.conjugate() * alpha2, c.conjugate() * alpha4)

    def frobenius3(self):
        (a0, a1), (b0, b1), (c0, c1) = self.coeffs
        a = FQ4(a0.conjugate(), -a1.conjugate() * alpha3)
        b = FQ4(b0.conjugate() * alpha3, b1.conjugate())
        c = FQ4(-c0.conjugate(), c1.conjugate() * alpha3)
        return FQ12(a, b, c)

    def frobenius6(self):
        a, b, c = self.coeffs
        return FQ12(a.conjugate(), -b.conjugate(), c.conjugate())


class ECC_Point:
    def __init__(self, *pt):  # 采用Jacobian射影坐标计算，输入仿射坐标后会转换为Jacobian射影坐标
        self.pt = pt if len(pt) == 3 else (*pt, pt[0].one())

    @classmethod
    def from_byte(cls, byte):  # 输入bytes类型仿射坐标，构建点对象
        fp_num = len(byte) // (N_SIZE << 1)  # 单个坐标包含的域元素个数
        if fp_num in (1, 2) and len(byte) % N_SIZE == 0:
            fp_list = [to_int(byte[i:i + N_SIZE]) for i in range(0, len(byte), N_SIZE)]  # 将bytes转换为域元素列表
            if fp_num == 1:
                return cls(FQ(fp_list[0]), FQ(fp_list[1]))
            x_list, y_list = fp_list[fp_num - 1::-1], fp_list[:fp_num - 1:-1]  # 从bytes到FQ2对象保存的域元素，需翻转高低位顺序
            return cls(FQ2(*x_list), FQ2(*y_list))
        return False

    def is_inf(self):
        return self[2].is_zero()

    def is_on_curve(self):  # 检查点是否满足曲线方程 y^2 == x^3 + b
        x, y, z = self.pt
        return y ** 2 == x ** 3 + (_b1 if type(x) is FQ else _b2) * z ** 6

    def double(self):
        x, y, z = self.pt
        _3x2, _2y = x.sqr() * 3, y * 2
        _4y2 = _2y.sqr()
        _4xy2 = x * _4y2
        x3 = _3x2.sqr() - _4xy2 * 2
        return ECC_Point(x3, _3x2 * (_4xy2 - x3) - _4y2.sqr() * _2_inv, _2y * z)

    def zero(self):
        cls = self[0].__class__
        return ECC_Point(cls.one(), cls.one(), cls.zero())

    def __add__(self, p2):
        if self.is_inf():
            return p2
        if p2.is_inf():
            return self
        (x1, y1, z1), (x2, y2, z2) = self.pt, p2.pt
        z1_2, z2_2 = z1.sqr(), z2.sqr()
        T1, T2 = x1 * z2_2, x2 * z1_2
        T3, T4, T5 = T1 - T2, y1 * z2_2 * z2, y2 * z1_2 * z1
        T6, T7, T3_2 = T4 - T5, T1 + T2, T3.sqr()
        T8, T9 = T4 + T5, T7 * T3_2
        x3 = T6.sqr() - T9
        T10 = T9 - x3 * 2
        y3 = (T10 * T6 - T8 * T3_2 * T3) * _2_inv
        z3 = z1 * z2 * T3
        return ECC_Point(x3, y3, z3)

    def multiply(self, n):  # 算法一：二进制展开法
        if n in (0, 1):
            return self if n else self.zero()
        Q = self
        for i in bin(n)[3:]:
            Q = Q.double() + self if i == '1' else Q.double()
        return Q

    def __mul__(self, n):  # 算法三：滑动窗法
        k = bin(n)[2:]
        l, r = len(k), 5  # 滑动窗口为5效果较好
        if r >= l:  # 如果窗口大于k的二进制位数，则本算法无意义
            return self.multiply(n)
        P_ = {1: self, 2: self.double()}  # 保存P[j]值的字典
        for i in range(1, 1 << (r - 1)):
            P_[(i << 1) + 1] = P_[(i << 1) - 1] + P_[2]
        t = r
        while k[t - 1] != '1':
            t -= 1
        hj = int(k[:t], 2)
        Q, j = P_[hj], t
        while j < l:
            if k[j] == '0':
                Q = Q.double()
                j += 1
            else:
                t = min(r, l - j)
                while k[j + t - 1] != '1':
                    t -= 1
                hj = int(k[j:j + t], 2)
                Q = Q.multiply(1 << t) + P_[hj]
                j += t
        return Q

    def __rmul__(self, n):
        return self.__mul__(n)

    def __eq__(self, p2):
        (x1, y1, z1), (x2, y2, z2) = self.pt, p2.pt
        z1_2, z2_2 = z1.sqr(), z2.sqr()
        return x1 * z2_2 == x2 * z1_2 and y1 * z2_2 * z2 == y2 * z1_2 * z1

    def __neg__(self):
        x, y, z = self.pt
        return ECC_Point(x, -y, z)

    def __getitem__(self, item):
        return self.pt[item]

    def __repr__(self):
        return '%s%s' % (self.__class__.__name__, self.normalize())

    def __bytes__(self):
        return to_byte(self.normalize(), N_SIZE if type(self[0]) is FQ else None)

    def normalize(self):
        x, y, z = self.pt
        if not hasattr(self, 'normalize_tuple'):
            if z != z.one():
                z_inv = z.inv()
                z_inv_2 = z_inv.sqr()
                x, y = x * z_inv_2, y * z_inv_2 * z_inv
            self.normalize_tuple = (x.n, y.n) if type(x) is FQ else (x, y)
        return self.normalize_tuple

    def frobenius(self):
        x, y, z = self.pt
        return ECC_Point(x.conjugate(), y.conjugate(), z.conjugate() * alpha1)

    def frobenius2(self):
        x, y, z = self.pt
        return ECC_Point(x, y, z * alpha2)


FQ2_one, FQ2_zero = FQ2(1, 0), FQ2(0, 0)  # FQ2单位元、零元
FQ4_one, FQ4_zero = FQ4(FQ2_one, FQ2_zero), FQ4()  # FQ4单位元、零元
FQ12_one = FQ12(FQ4_one, FQ4_zero, FQ4_zero)  # FQ12单位元
P1 = ECC_Point(FQ(x_p1), FQ(y_p1))  # 群G1的生成元
P2 = ECC_Point(FQ2(*x_p2[::-1]), FQ2(*y_p2[::-1]))  # 群G2的生成元
_b1, _b2 = FQ(5), FQ2(0, 5)  # b2=βb=(1,0)*5
alpha1 = 0X3F23EA58E5720BDB843C6CFA9C08674947C5C86E0DDD04EDA91D8354377B698B  # -2^((q - 1)/12)
alpha2 = 0XF300000002A3A6F2780272354F8B78F4D5FC11967BE65334  # -2^((q - 1)/6)
alpha3 = 0X6C648DE5DC0A3F2CF55ACC93EE0BAF159F9D411806DC5177F5B21FD3DA24D011  # -2^((q - 1)/4)
alpha4 = 0XF300000002A3A6F2780272354F8B78F4D5FC11967BE65333  # -2^((q - 1)/3)
alpha5 = 0X2D40A38CF6983351711E5F99520347CC57D778A9F8FF4C8A4C949C7FA2A96686
_2_inv = 0X5B2000000151D378EB01D5A7FAC763A290F949A58D3D776DF2B7CD93F1A8A2BF  # 1/2
_3div2 = 0X5B2000000151D378EB01D5A7FAC763A290F949A58D3D776DF2B7CD93F1A8A2C0  # 3/2
R_ate_a_NAF = '0100000000000000000000000000000000000010001020200020200101000020'  # a=6t+2的二进制非相邻表示(2-NAF)（去首10）
hlen = 320  # 8 * ceil(5 * log(N, 2) / 32)
_t, _6t, _6t_3 = 0x600000000058F98A, 0X2400000000215D93C, 0X2400000000215D93F


# 输入系数值和点P，求线函数值
def g_value(a_tuple, P):
    (a0, a1, a4), (xP, yP) = a_tuple, P
    return FQ12(FQ4(a0, a1 * yP), FQ4_zero, FQ4(a4 * xP, FQ2_zero))


# 获取线函数g T,Q(P)的系数值（分母在最终模幂时值为1，可消去）
def get_g_a_tuple(T, Q):
    (xT, yT, zT), (xQ, yQ, zQ) = T, Q
    zT_2, zQ_2 = zT.sqr(), zQ.sqr()
    zQ_3, t1 = zQ * zQ_2, (xT * zQ_2 - xQ * zT_2) * zT * zQ
    a1, t2 = t1 * zQ_3, (yT * zQ_3 - yQ * zT * zT_2) * zQ
    a0, a4 = t1 * yQ - t2 * xQ, t2 * zQ_2
    return a0, a1, a4


# 线函数g T,Q(P)，求过点T和Q的直线在P上的值
def g(T, Q, nP):
    return g_value(get_g_a_tuple(T, Q), nP)


# 获取线函数g T,T(P)的系数值（分母在最终模幂时值为1，可消去），利用中间值完成倍点计算
def get_g2_a_tuple(T):
    x, y, z = T
    _z2, _3x2, _2y = z.sqr(), x.sqr() * 3, y * 2
    _4y2, _2yz = _2y.sqr(), _2y * z
    a1, a0, a4, _4xy2 = _z2 * _2yz, _4y2 * _2_inv - _3x2 * x, _3x2 * _z2, x * _4y2
    x3 = _3x2.sqr() - _4xy2 * 2
    y3 = _3x2 * (_4xy2 - x3) - _4y2.sqr() * _2_inv
    return (a0, a1, a4), ECC_Point(x3, y3, _2yz)


# 线函数g T,T(P)，求过点T的切线在P上的值，利用中间值完成倍点计算
def g2(T, nP):
    a_tuple, double_T = get_g2_a_tuple(T)
    return g_value(a_tuple, nP), double_T


# BN曲线上R_ate对的计算
def e(P, Q):
    nQ, nP_xy = -Q, (-P).normalize()
    f, T = g2(Q, nP_xy)
    for ai in R_ate_a_NAF:
        new_g, T = g2(T, nP_xy)
        f = f.sqr() * new_g
        if ai == '1':
            f, T = f * g(T, Q, nP_xy), T + Q
        elif ai == '2':  # 用2代替-1
            f, T = f * g(T, nQ, nP_xy), T + nQ
    Q1, nQ2 = Q.frobenius(), nQ.frobenius2()
    return final_exp(f * g(T, Q1, nP_xy) * g(T + Q1, nQ2, nP_xy))


# 最终模幂
def final_exp(f):
    m = f.frobenius6() * f.inv()  # f^(p^6 - 1)
    s = m.frobenius2() * m  # m^(p^2 + 1)
    return hard_part(s)


# 最终模幂的困难部分 s^(p^3 + (6t^2+1)p^2 + (-36t^3-18t^2-12t+1)p + (-36t^3-30t^2-18t-2))
def hard_part(s):
    s_6t = s ** _6t
    s_6t2 = s_6t ** _t
    s_36t3_18t2_12t, a2 = s_6t2 ** _6t_3 * s_6t.GT_sqr(), s_6t2 * s
    a1, a0 = s_36t3_18t2_12t.frobenius6() * s, (s_36t3_18t2_12t * s_6t * a2.GT_sqr()).frobenius6()
    return s.frobenius3() * a2.frobenius2() * a1.frobenius() * a0


# 获取线函数的系数值序列
def get_a_list(Q):
    a_tuple, T = get_g2_a_tuple(Q)
    a_list, nQ = [a_tuple], -Q
    for ai in R_ate_a_NAF:
        a_tuple, T = get_g2_a_tuple(T)
        a_list.append(a_tuple)
        if ai != '0':
            a_list.append(get_g_a_tuple(T, nQ if ai == '2' else Q))
            T = T + (nQ if ai == '2' else Q)
    Q1, nQ2 = Q.frobenius(), nQ.frobenius2()
    return a_list + [get_g_a_tuple(T, Q1), get_g_a_tuple(T + Q1, nQ2)]


def e_fast(P, a_list):
    nP_xy = (-P).normalize()
    f, i = g_value(a_list[0], nP_xy), 1
    for ai in R_ate_a_NAF:
        f, i = f.sqr() * g_value(a_list[i], nP_xy), i + 1
        if ai != '0':
            f, i = f * g_value(a_list[i], nP_xy), i + 1
    return final_exp(f * g_value(a_list[i], nP_xy) * g_value(a_list[-1], nP_xy))


# 获取Comb固定基的预计算二维表（num*255个FQ12元素），num可取1,2,4,8,16,32
def get_comb_list(n, num=1):
    comb_list, step, tmp = [[FQ12_one, n]], 32 // num, n
    for i in range(num - 1):  # 每行列表初始化（高幂次在前）
        for _ in range(step):
            tmp = tmp.GT_sqr()
        comb_list.insert(0, [FQ12_one, tmp])
    for i in range(7):
        for comb_line in reversed(comb_list):
            for _ in range(step):
                tmp = tmp.GT_sqr()
            comb_line += [tmp] + [tmp * c for c in comb_line[1:]]
    return comb_list


# 二维Comb固定基的幂运算
def comb_pow(r, comb_list):
    r_bin, res, step, num = '0' * (256 - r.bit_length()) + bin(r)[2:], FQ12_one, 32 // len(comb_list), len(comb_list)
    for i in range(step):
        tmp = comb_list[0][int(''.join(r_bin[j] for j in range(i, 256, 32)), 2)]
        for k in range(1, num):
            tmp = tmp * comb_list[k][int(''.join(r_bin[j] for j in range(i + step * k, 256, 32)), 2)]
        res = tmp if res is FQ12_one else res.GT_sqr() * tmp
    return res


# 获取固定点乘的预计算表（32行256列的椭圆曲线点矩阵）
def get_kP_list(P):
    one, kP_list = P, []
    for i in range(32):
        line_list = [0, one]  # O, P
        for j in range(1, 128):
            line_list.append(line_list[j].double())  # 2j·P
            line_list.append(line_list[-1] + one)  # (2j+1)·P
        kP_list.append(line_list)
        one = line_list[128].double() if i < 31 else 0
    return kP_list


# 使用预计算表的快速点乘
def fast_kG(k, kP_list):
    P_list = [kP_list[i][byte] for i, byte in enumerate(k.to_bytes(32, byteorder='little')) if byte]
    return sum(P_list[1:], P_list[0])


# SM9算法(GB_T 38635.2-2020) 5.3.6定义的密钥派生函数
# Z为bytes类型，klen表示输出密钥比特长度（8的倍数）；输出为bytes类型
def KDF(Z, klen=KEY_LEN):
    ksize, K = klen >> 3, bytearray()
    for ct in range(1, ceil(ksize / HASH_SIZE) + 1):
        K.extend(sm3(Z + to_byte(ct, 4)))
    return K[:ksize]


# SM9算法(GB_T 38635.2-2020) 5.3.2.2和5.3.2.3定义的密码函数
def H(i, Z):
    Ha = to_int(KDF(to_byte(i, 1) + Z, hlen))
    return Ha % (N - 1) + 1


# SM9算法(GB_T 38635.2-2020) 5.3.5定义的消息认证码函数
def MAC(K2, Z):
    return sm3(Z + K2)


# 定义常用联系人的具名元组
SM9_contacts = namedtuple('SM9_contacts', 'k_Q_list P_a_list')


class SM9:  # SM9算法(GB_T 38635.2-2020)
    def __init__(self, ID='', ds=None, Ppub_s=None, de=None, Ppub_e=None, hid_s=1, hid_e=3, ks=None, ke=None):
        self.ID, self.ID_byte, self.hid_s_byte, self.hid_e_byte = ID, to_byte(ID), to_byte(hid_s, 1), to_byte(hid_e, 1)
        if ks:  # 作为密钥生成中心，给定签名主私钥（若要随机生成，可指定ks=-1）
            self.ks = ks if 0 < ks < N else randrange(1, N)
            self.Ppub_s = fast_kG(self.ks, _kP2)
        if ke:  # 作为密钥生成中心，给定加密主私钥（若要随机生成，可指定ke=-1）
            self.ke = ke if 0 < ke < N else randrange(1, N)
            self.Ppub_e = fast_kG(self.ke, _kP1)
        if ds and Ppub_s:  # 作为用户，给定用户签名私钥和签名主公钥
            self.k_ds_list, self.Ppub_s, self.gs = get_kP_list(ds), Ppub_s, e(P1, Ppub_s)
            self.gs_comb_list = get_comb_list(self.gs)
        if de and Ppub_e:  # 作为用户，给定用户加密私钥和加密主公钥
            self.de_a_list, self.Ppub_e, self.ge = get_a_list(de), Ppub_e, e(Ppub_e, P2)
            self.k_Pe_list, self.ge_comb_list = get_kP_list(Ppub_e), get_comb_list(self.ge)
        self.contacts = {}

    def KGC_gen_user(self, ID):
        ID_byte, ds, Ppub_s, de, Ppub_e = to_byte(ID), None, None, None, None
        if hasattr(self, 'ks'):
            t1 = (H(1, ID_byte + self.hid_s_byte) + self.ks) % N
            if t1 == 0:  # 需重新产生签名主密钥，并更新所有用户的签名密钥
                return False
            t2 = self.ks * mod_inv(t1, N) % N
            ds, Ppub_s = fast_kG(t2, _kP1), self.Ppub_s  # 用户签名私钥和签名主公钥
        if hasattr(self, 'ke'):
            t1 = (H(1, ID_byte + self.hid_e_byte) + self.ke) % N
            if t1 == 0:  # 需重新产生加密主密钥，并更新所有用户的加密密钥
                return False
            t2 = self.ke * mod_inv(t1, N) % N
            de, Ppub_e = fast_kG(t2, _kP2), self.Ppub_e  # 用户加密私钥和加密主公钥
        return SM9(ID, ds, Ppub_s, de, Ppub_e, self.hid_s_byte, self.hid_e_byte)

    # 添加常用联系人ID
    def add_contacts(self, ID):
        ID_byte, k_Q_list, P_a_list = to_byte(ID), None, None
        if hasattr(self, 'Ppub_e'):  # 用于密钥交换双方、封装、加密
            k_Q_list = get_kP_list(fast_kG(H(1, ID_byte + self.hid_e_byte), _kP1) + self.Ppub_e)
        if hasattr(self, 'Ppub_s'):  # 用于验签
            P_a_list = get_a_list(fast_kG(H(1, ID_byte + self.hid_s_byte), _kP2) + self.Ppub_s)
        self.contacts[ID] = SM9_contacts(k_Q_list, P_a_list)

    # 6.2 数字签名生成算法
    def sign(self, M, r=None, outbytes=True):
        l = 0
        while l == 0:
            r = r if r else randrange(1, N)  # A2
            w = bytes(self.gs_pow(r))  # A3
            h = H(2, to_byte(M) + w)  # A4
            l = (r - h) % N  # A5
        S = fast_kG(l, self.k_ds_list)  # A6
        return to_byte([h, S]) if outbytes else (h, S)

    # 6.4 数字签名验证算法
    def verify(self, ID, M_, sig):
        h_, S_ = (to_int(sig[:N_SIZE]), ECC_Point.from_byte(sig[N_SIZE:])) if type(sig) is bytes else sig
        if not 0 < h_ < N or not S_ or not S_.is_on_curve():  # B1、B2
            return False
        t = self.gs_pow(h_)  # B4
        if ID in self.contacts:
            u = e_fast(S_, self.contacts[ID].P_a_list)
        else:
            h1 = H(1, to_byte(ID) + self.hid_s_byte)  # B5
            P = fast_kG(h1, _kP2) + self.Ppub_s  # B6
            u = e(S_, P)  # B7
        w_ = bytes(u * t)  # B8
        h2 = H(2, to_byte(M_) + w_)  # B9
        return h_ == h2

    # A 发起协商（也可用作B生成rB、RB；outbytes=True时输出bytes）
    # 7.2 密钥交换协议 A1-A3
    def agreement_initiate(self, IDB, r=None, outbytes=True):
        rA = r if r else randrange(1, N)  # A2
        RA = fast_kG(rA, self.contacts[IDB].k_Q_list) if IDB in self.contacts else \
            fast_kG(H(1, to_byte(IDB) + self.hid_e_byte) * rA % N, _kP1) + fast_kG(rA, self.k_Pe_list)  # A1/A3
        return rA, bytes(RA) if outbytes else RA

    # B 响应协商（option=True时计算选项部分）
    # 7.2 密钥交换协议 B1-B6
    def agreement_response(self, RA, IDA, option=False, rB=None, klen=KEY_LEN, outbytes=True):
        RA = ECC_Point.from_byte(RA) if type(RA) is bytes else RA
        if not RA or not RA.is_on_curve():  # B4
            return False, 'RA不属于椭圆曲线群G1'
        rB, RB = self.agreement_initiate(IDA, rB, outbytes)  # B1-B3
        g1, g2 = self.e_de(RA), bytes(self.ge_pow(rB))  # B4
        g1, g3 = bytes(g1), bytes(g1 ** rB)  # B4
        tmp_byte = to_byte([IDA, self.ID_byte, RA, RB])
        SKB = KDF(tmp_byte + g1 + g2 + g3, klen)  # B5
        if not option:
            return True, (RB, SKB)
        self.tmp_byte2 = g1 + sm3(g2 + g3 + tmp_byte)
        SB = sm3(to_byte(0x82, 1) + self.tmp_byte2)  # B6（可选部分）
        return True, (RB, SKB, SB)

    # A 协商确认
    # 7.2 密钥交换协议 A5-A8
    def agreement_confirm(self, rA, RA, RB, IDB, SB=None, option=False, klen=KEY_LEN):
        RB = ECC_Point.from_byte(RB) if type(RB) is bytes else RB
        if not RB or not RB.is_on_curve():  # A5
            return False, 'RB不属于椭圆曲线群G1'
        g1_, g2_ = bytes(self.ge_pow(rA)), self.e_de(RB)  # A5
        g2_, g3_ = bytes(g2_), bytes(g2_ ** rA)  # A5
        tmp_byte = to_byte([self.ID_byte, IDB, RA, RB])
        if option and SB:  # A6（可选部分）
            tmp_byte2 = g1_ + sm3(g2_ + g3_ + tmp_byte)
            S1 = sm3(to_byte(0x82, 1) + tmp_byte2)
            if S1 != SB:
                return False, 'S1 != SB'
        SKA = KDF(tmp_byte + g1_ + g2_ + g3_, klen)  # A7
        if not option or not SB:
            return True, SKA
        SA = sm3(to_byte(0x83, 1) + tmp_byte2)  # A8
        return True, (SKA, SA)

    # B 协商确认（可选部分）
    # 7.2 密钥交换协议 B8
    def agreement_confirm2(self, SA):
        if not hasattr(self, 'tmp_byte2'):
            return False, 'step error'
        S2 = sm3(to_byte(0x83, 1) + self.tmp_byte2)
        if S2 == SA:
            del self.tmp_byte2
            return True, ''
        return False, 'S2 != SA'

    # 8.2 密钥封装算法
    def encaps(self, IDB, klen, r=None, outbytes=True):
        K = bytes()
        while K == bytes(len(K)):
            r, C = self.agreement_initiate(IDB, r, outbytes)  # A1-A3
            w = bytes(self.ge_pow(r))  # A5
            K = KDF(to_byte([C, w, IDB]), klen)
        return K, C

    # 8.4 解封装算法
    def decaps(self, C, klen):
        C = ECC_Point.from_byte(C) if type(C) is bytes else C
        if not C or not C.is_on_curve():  # B1
            return False, 'C不属于椭圆曲线群G1'
        w_ = bytes(self.e_de(C))  # B2
        K_ = KDF(to_byte([C, w_, self.ID_byte]), klen)  # B3
        return (True, K_) if K_ != bytes(len(K_)) else (False, 'K为全0比特串')

    # 9.2 加密算法
    def encrypt(self, IDB, M, r=None, outbytes=True):
        M = to_byte(M)
        K, C1 = self.encaps(IDB, (len(M) << 3) + K2_len, r, outbytes)  # A1-A6.a.1
        K1, K2 = K[:len(M)], K[len(M):]  # A6.a.1
        C2 = bytes(M[i] ^ K1[i] for i in range(len(M)))  # A6.a.2
        C3 = MAC(K2, C2)  # A7
        return to_byte([C1, C3, C2]) if outbytes else (C1, C3, C2)

    # 9.4 解密算法
    def decrypt(self, C):
        C3_start, C3_end = N_SIZE << 1, (N_SIZE << 1) + HASH_SIZE
        C1, C3, C2 = (C[:C3_start], C[C3_start:C3_end], C[C3_end:]) if type(C) is bytes else C
        res, K_ = self.decaps(C1, (len(C2) << 3) + K2_len)  # B1-B3.a.1
        if not res:
            return False, K_.replace('C', 'C1')
        K1_, K2_ = K_[:len(C2)], K_[len(C2):]  # B3.a.1
        if K1_ == bytes(len(K_)):
            return False, 'K1\'为全0比特串'
        u = MAC(K2_, C2)  # B4
        if u != C3:
            return False, 'u != C3'
        return True, bytes(C2[i] ^ K1_[i] for i in range(len(C2)))  # B3.a.2

    def e_de(self, P):
        return e_fast(P, self.de_a_list)

    def gs_pow(self, r):
        return comb_pow(r, self.gs_comb_list)

    def ge_pow(self, r):
        return comb_pow(r, self.ge_comb_list)


_kP1, _kP2 = [], []  # P1、P2点的预计算表
_SM9kG_file = './SM9_kG.bin'  # 预计算数据文件的位置
if os.path.exists(_SM9kG_file):
    print('读取预计算数据文件：%s' % _SM9kG_file)
    time_1 = time.perf_counter()
    with open(_SM9kG_file, 'rb') as f:  # 读取预计算数据文件
        data = f.read()
        G1_size, G2_size = N_SIZE << 1, N_SIZE << 2  # G1点坐标字节数、G2点坐标字节数
        P1_line, line = 255 * G1_size, 255 * (G1_size + G2_size)  # 一行G1点坐标字节数、一行总字节数
        for i in range(0, N_SIZE * line, line):
            _kP1.append([0] + [ECC_Point.from_byte(data[j:j + G1_size]) for j in range(i, i + P1_line, G1_size)])
            _kP2.append([0] + [ECC_Point.from_byte(data[j:j + G2_size]) for j in range(i + P1_line, i + line, G2_size)])
    time_2 = time.perf_counter()
    print('耗时：%.2f ms' % ((time_2 - time_1) * 1000))
else:  # 预计算数据文件不存在
    print('预计算数据文件不存在，即刻生成...')
    time_1 = time.perf_counter()
    _kP1, _kP2 = get_kP_list(P1), get_kP_list(P2)  # 生成P1、P2点的预计算表
    with open(_SM9kG_file, 'wb') as f:  # 将预计算表写入二进制文件
        f.write(b''.join(map(bytes, [P for x, y in zip(_kP1, _kP2) for P in x[1:] + y[1:]])))
    time_2 = time.perf_counter()
    print('写入预计算数据文件耗时：%.2f s' % (time_2 - time_1))


# ————————————————————————————————————论文—国密算法SM9的性能优化方法—实验代码————————————————————————————————————
# 获取Comb固定基的预计算表（256个FQ12的列表）
def get_comb_list2(n):
    # comb_list = [FQ12_one, n]
    # for i in range(7):
    #     tmp = comb_list[2**i]
    #     for _ in range(32):
    #         tmp = tmp.sqr2()
    #     comb_list += [tmp * c for c in comb_list]
    # return comb_list
    comb_list, tmp = [n], n
    for i in range(7):
        for _ in range(32):
            tmp = tmp.GT_sqr()
        comb_list += [tmp] + [tmp * c for c in comb_list]
    return [FQ12_one] + comb_list


# Comb固定基的幂运算
def comb_pow2(r, comb_list):
    r_bin, res = '0' * (256 - r.bit_length()) + bin(r)[2:], FQ12_one
    for i in range(32):
        a = int(''.join(r_bin[j] for j in range(i, 256, 32)), 2)
        res = comb_list[a] if res is FQ12_one else res.GT_sqr() * comb_list[a]
    return res


# 获取固定点乘的预计算表（低效版）
def get_kP_list2(P):
    kP_list = [[0] + [P * k for k in range(1, 256)]]
    for i in range(31):
        kP_list.append([0] + [Q * 256 for Q in kP_list[i]][1:])
    return kP_list


# 采用预计算的Miller算法
def Miller_fast(P, a_list):
    nP_xy = (-P).normalize()
    f, i = g_value(a_list[0], nP_xy), 1
    for ai in R_ate_a_NAF:
        f, i = f.sqr() * g_value(a_list[i], nP_xy), i + 1
        if ai != '0':
            f, i = f * g_value(a_list[i], nP_xy), i + 1
    return f * g_value(a_list[i], nP_xy) * g_value(a_list[-1], nP_xy)


# 普通Miller算法
def Miller(P, Q):
    nQ, nP_xy = -Q, (-P).normalize()
    f, T = g2(Q, nP_xy)
    for ai in R_ate_a_NAF:
        new_g, T = g2(T, nP_xy)
        f = f.sqr() * new_g
        if ai == '1':
            f, T = f * g(T, Q, nP_xy), T + Q
        elif ai == '2':  # 用2代替-1
            f, T = f * g(T, nQ, nP_xy), T + nQ
    Q1, nQ2 = Q.frobenius(), nQ.frobenius2()
    return f * g(T, Q1, nP_xy) * g(T + Q1, nQ2, nP_xy)


# 最终模幂的困难部分（文献4版本）
def hard_part2(f):
    f_t, f_p, f_p2 = f ** _t, f.frobenius(), f.frobenius2()
    f_t2, f_tp, f_p3 = f_t ** _t, f_t.frobenius(), f_p.frobenius2()
    f_t3, f_t2p, f_t2p2 = f_t2 ** _t, f_t2.frobenius(), f_t2.frobenius2()
    f_t3p = f_t3.frobenius()
    return f_p * f_p2 * f_p3 * ((((f_t3 * f_t3p).GT_sqr() * f_t * f_t2p)**3 * f_t2**5 * f_tp.GT_sqr() * f_t2p2.frobenius6())**6 * f.GT_sqr()).frobenius6()


# GT上的普通模幂
def pow_G6(x, y):
    t = x
    for ri in bin(y)[3:]:
        t = t.GT_sqr() * x if ri == '1' else t.GT_sqr()
    return t


# FQ12上的普通模幂
def pow_fq12(x, y):
    t = x
    for ri in bin(y)[3:]:
        t = t.sqr() * x if ri == '1' else t.sqr()
    return t


# 表2测试项
def test1(test_num):
    print('\n---------------------------生成G1点乘预计算数据---------------------------')
    time_1 = time.perf_counter()
    # 本文
    kP1_list = get_kP_list(P1)
    time_2 = time.perf_counter()
    # 对照组
    kP1_list2 = get_kP_list2(P1)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000, (time_3 - time_2) / time_relative))
    assert kP1_list == kP1_list2

    print('\n---------------------------生成G2点乘预计算数据---------------------------')
    time_1 = time.perf_counter()
    # 本文
    kP2_list = get_kP_list(P2)
    time_2 = time.perf_counter()
    # 对照组
    kP2_list2 = get_kP_list2(P2)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000, (time_3 - time_2) / time_relative))
    assert kP2_list == kP2_list2

    k_list = [randrange(1, N) for _ in range(test_num)]
    print('\n---------------------------G1点乘---------------------------')
    print('测试%d次 [1, N-1] 范围的随机数与P1点相乘' % test_num)
    res_fast, res_normal = [], []
    time_1 = time.perf_counter()
    # 采用预计算的G1点乘
    for k in k_list:
        res_fast.append(fast_kG(k, kP1_list))
    time_2 = time.perf_counter()
    # 普通G1点乘
    for k in k_list:
        res_normal.append(P1 * k)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('预计算\t耗时%.2f ms \t\t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('普通\t\t耗时%.2f ms \t\t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    assert res_fast == res_normal

    print('\n---------------------------G2点乘---------------------------')
    print('测试%d次 [1, N-1] 范围的随机数与P2点相乘' % test_num)
    res_fast, res_normal = [], []
    time_1 = time.perf_counter()
    # 采用预计算的G2点乘
    for k in k_list:
        res_fast.append(fast_kG(k, kP2_list))
    time_2 = time.perf_counter()
    # 普通G2点乘
    for k in k_list:
        res_normal.append(P2 * k)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('预计算\t耗时%.2f ms \t\t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('普通\t\t耗时%.2f ms \t\t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    assert res_fast == res_normal

    print('\n---------------------------Miller算法---------------------------')
    time_1 = time.perf_counter()
    # 生成Miller算法预计算数据
    P2_a_list = get_a_list(P2)
    time_2 = time.perf_counter()
    # 采用预计算的Miller算法
    res_fast = Miller_fast(P1, P2_a_list)
    time_3 = time.perf_counter()
    # 普通Miller算法
    res_normal = Miller(P1, P2)
    time_4 = time.perf_counter()
    time_relative = time_4 - time_3
    print('生成Miller算法预计算数据\t耗时%.2f ms  \t相对耗时%.2f' % ((time_2 - time_1) * 1000, (time_2 - time_1) / time_relative))
    print('采用预计算的Miller算法\t\t耗时%.2f ms  \t相对耗时%.2f' % ((time_3 - time_2) * 1000, (time_3 - time_2) / time_relative))
    print('普通Miller算法\t\t\t耗时%.2f ms  \t相对耗时%.2f' % ((time_4 - time_3) * 1000, (time_4 - time_3) / time_relative))
    assert res_fast == res_normal

    print('\n---------------------------最终模幂困难部分---------------------------')
    m = res_fast.frobenius6() * res_fast.inv()  # 转变为GT上的元素
    s = m.frobenius2() * m  # 完成简单部分
    time_1 = time.perf_counter()
    # 本文
    res = hard_part(s)
    time_2 = time.perf_counter()
    # 对照组
    res2 = hard_part2(s)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000, (time_3 - time_2) / time_relative))
    assert res == res2

    print('\n---------------------------高次模幂---------------------------')
    print('测试%d次 [1, N-1] 范围的随机数作为指数参与FQ12上的模幂' % test_num)
    res_G6_2NAF, res_G6_normal, res_FQ12_normal, res_Comb = [], [], [], []
    time_1 = time.perf_counter()
    # GT上的2-NAF模幂
    for k in k_list:
        res_G6_2NAF.append(res ** k)
    time_2 = time.perf_counter()
    # GT上的普通模幂
    for k in k_list:
        res_G6_normal.append(pow_G6(res, k))
    time_3 = time.perf_counter()
    # FQ12上的普通模幂
    for k in k_list:
        res_FQ12_normal.append(pow_fq12(res, k))
    time_4 = time.perf_counter()
    # 生成Comb固定基预计算数据
    comb_list = get_comb_list2(res)
    time_5 = time.perf_counter()
    # 基于Comb固定基的模幂
    for k in k_list:
        res_Comb.append(comb_pow2(k, comb_list))
    time_6 = time.perf_counter()
    time_relative = time_4 - time_3
    print('分圆循环子群上的2-NAF模幂\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('分圆循环子群上的普通模幂\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    print('FQ12上的普通模幂\t\t\t耗时%.2f ms  \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
    print('生成Comb固定基预计算数据\t耗时%.2f ms  \t相对耗时%.2f' % ((time_5 - time_4) * 1000, (time_5 - time_4) / time_relative))
    print('基于Comb固定基的模幂\t\t耗时%.2f ms  \t相对耗时%.2f' % ((time_6 - time_5) * 1000 / test_num, (time_6 - time_5) / time_relative))
    assert res_G6_2NAF == res_G6_normal == res_FQ12_normal == res_Comb


# ————————————————————————————————————论文—国密算法SM9的计算性能改进方法—实验代码————————————————————————————————————
def agreement_initiate2(hid_e_byte, Ppub_e, IDB, r=None, outbytes=True):
    QB = fast_kG(H(1, to_byte(IDB) + hid_e_byte), _kP1) + Ppub_e  # A1
    rA = r if r else randrange(1, N)  # A2
    RA = QB * rA  # A3
    return rA, bytes(RA) if outbytes else RA


# 测试项
def test2(test_num):
    IDB = 'BILL456@YAHOO.COM'
    kgc = SM9(ke=-1, ks=-1)
    sm9_A = kgc.KGC_gen_user('IDA')
    k_list = [randrange(1, N) for _ in range(test_num)]

    print('\n---------------------------生成Comb固定基预计算数据---------------------------')
    time_1 = time.perf_counter()
    # 原始
    gs_comb_list0 = get_comb_list2(sm9_A.gs)
    time_2 = time.perf_counter()
    # n=1
    gs_comb_list1 = get_comb_list(sm9_A.gs, 1)
    time_3 = time.perf_counter()
    # n=2
    gs_comb_list2 = get_comb_list(sm9_A.gs, 2)
    time_4 = time.perf_counter()
    # n=4
    gs_comb_list4 = get_comb_list(sm9_A.gs, 4)
    time_5 = time.perf_counter()
    # n=8
    gs_comb_list8 = get_comb_list(sm9_A.gs, 8)
    time_6 = time.perf_counter()
    # n=16
    gs_comb_list16 = get_comb_list(sm9_A.gs, 16)
    time_7 = time.perf_counter()
    # n=32
    gs_comb_list32 = get_comb_list(sm9_A.gs, 32)
    time_8 = time.perf_counter()
    time_relative = time_3 - time_2
    print('原始\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000, time_relative / (time_2 - time_1)))
    print('n=1\t\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000, time_relative / (time_3 - time_2)))
    print('n=2\t\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000, time_relative / (time_4 - time_3)))
    print('n=4\t\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000, time_relative / (time_5 - time_4)))
    print('n=8\t\t耗时%.2f ms \t相对速率%.2f' % ((time_6 - time_5) * 1000, time_relative / (time_6 - time_5)))
    print('n=16\t耗时%.2f ms \t相对速率%.2f' % ((time_7 - time_6) * 1000, time_relative / (time_7 - time_6)))
    print('n=32\t耗时%.2f ms \t相对速率%.2f' % ((time_8 - time_7) * 1000, time_relative / (time_8 - time_7)))
    assert gs_comb_list0 == gs_comb_list1[-1] == gs_comb_list2[-1] == gs_comb_list4[-1] == gs_comb_list8[-1] == gs_comb_list16[-1] == gs_comb_list32[-1]

    print('\n---------------------------基于Comb固定基的模幂---------------------------')
    print('测试%d次 [1, N-1] 范围的随机数作为指数参与模幂' % test_num)
    res0, res1, res2, res4, res8, res16, res32 = [], [], [], [], [], [], []
    time_1 = time.perf_counter()
    # 原始
    for k in k_list:
        res0.append(sm9_A.gs ** k)
    time_2 = time.perf_counter()
    # n=1
    for k in k_list:
        res1.append(comb_pow(k, gs_comb_list1))
    time_3 = time.perf_counter()
    # n=2
    for k in k_list:
        res2.append(comb_pow(k, gs_comb_list2))
    time_4 = time.perf_counter()
    # n=4
    for k in k_list:
        res4.append(comb_pow(k, gs_comb_list4))
    time_5 = time.perf_counter()
    # n=8
    for k in k_list:
        res8.append(comb_pow(k, gs_comb_list8))
    time_6 = time.perf_counter()
    # n=16
    for k in k_list:
        res16.append(comb_pow(k, gs_comb_list16))
    time_7 = time.perf_counter()
    # n=32
    for k in k_list:
        res32.append(comb_pow(k, gs_comb_list32))
    time_8 = time.perf_counter()
    time_relative = time_2 - time_1
    print('原始\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
    print('n=1\t\t耗时%.2f ms \t\t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
    print('n=2\t\t耗时%.2f ms \t\t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, time_relative / (time_4 - time_3)))
    print('n=4\t\t耗时%.2f ms \t\t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, time_relative / (time_5 - time_4)))
    print('n=8\t\t耗时%.2f ms \t\t相对速率%.2f' % ((time_6 - time_5) * 1000 / test_num, time_relative / (time_6 - time_5)))
    print('n=16\t耗时%.2f ms \t\t相对速率%.2f' % ((time_7 - time_6) * 1000 / test_num, time_relative / (time_7 - time_6)))
    print('n=32\t耗时%.2f ms \t\t相对速率%.2f' % ((time_8 - time_7) * 1000 / test_num, time_relative / (time_8 - time_7)))
    assert res0 == res1 == res2 == res4 == res8 == res16 == res32

    print('\n---------------------------计算r·Q(ID)---------------------------')
    print('测试%d次 [1, N-1] 范围的随机数与QB点乘' % test_num)
    res_normal, res_fast, res_ID = [], [], []
    time_1 = time.perf_counter()
    # 优化前
    for k in k_list:
        res_normal.append(agreement_initiate2(sm9_A.hid_e_byte, sm9_A.Ppub_e, IDB, k))
    time_2 = time.perf_counter()
    # 优化后
    for k in k_list:
        res_fast.append(sm9_A.agreement_initiate(IDB, k))
    time_3 = time.perf_counter()
    # A添加联系人IDB
    sm9_A.add_contacts(IDB)
    time_4 = time.perf_counter()
    # 固定ID
    for k in k_list:
        res_ID.append(sm9_A.agreement_initiate(IDB, k))
    time_5 = time.perf_counter()
    time_relative = time_2 - time_1
    print('优化前\t耗时%.2f ms \t\t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
    print('优化后\t耗时%.2f ms \t\t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
    print('添加ID\t耗时%.2f ms' % ((time_4 - time_3) * 1000))
    print('固定ID\t耗时%.2f ms \t\t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, time_relative / (time_5 - time_4)))
    assert res_fast == res_normal == res_ID


# ————————————————————————————————————论文—基于国密算法SM9的加法同态加密方案—实验代码————————————————————————————————————
# 文献[1]：唐飞, 凌国玮, 单进勇. 基于国密SM2和SM9的加法同态加密方案[J]. 密码学报, 2022, 9(3): 535-549

# —————————————————————————————————论文—群GT上小指数离散对数问题的高效求解（英文）—实验代码————————————————————————————————
# ——————————FastGTDLP: Efficient Algorithm for Small-Exponent Discrete Logarithm Problem over Group GT——————————
MASK_32 = (1 << 32) - 1
class SM9_HOMO(SM9):
    def __init__(self, sm9, key_size=8, l1=24, l2=16, hash_start=0, coor_start=24):
        self.de_a_list, self.ge, self.hid_e_byte = sm9.de_a_list, sm9.ge, sm9.hid_e_byte
        self.k_Pe_list, self.ge_comb_list = sm9.k_Pe_list, sm9.ge_comb_list
        self.key_size, self.l1, self.l2 = key_size, l1, l2  # 字典键的字节数，l1和l2的位数
        self.hash_start, self.coor_start = hash_start, coor_start  # 字典文件1/2的键在原始字节串中的起始位置
        hash_dir_try = 'SM9_homo_hash_%d_%d_%d.bin' % (l1, key_size, hash_start)  # 字典文件1的可能路径
        coor_dir_try = 'SM9_homo_coor_%d_%d_%d.bin' % (l1, key_size, coor_start)  # 字典文件2的可能路径
        hash_dir, coor_dir = None, None  # 字典文件1/2的路径
        if os.path.exists(hash_dir_try):
            hash_dir = hash_dir_try
        elif os.path.exists('hggm/' + hash_dir_try):  # 执行不同的测试文件，相对路径不同
            hash_dir = 'hggm/' + hash_dir_try
        if os.path.exists(coor_dir_try):
            coor_dir = coor_dir_try
        elif os.path.exists('hggm/' + coor_dir_try):  # 执行不同的测试文件，相对路径不同
            coor_dir = 'hggm/' + coor_dir_try
        # if hash_dir:
        #     self.hash_dict = self.read_dict_file(hash_dir)  # g^m的hash值（key_size字节） → m（1<=m<=2^l1）
        self.lowFq_dict = self.read_dict_file(coor_dir, True)  # g^m的最低位FQ（key_size字节） → m（1<=m<=2^l1）
        self.highFq_dict = self.read_dict_file(coor_dir + '2', True)  # g^m的最高位FQ（key_size字节） → m（1<=m<=2^l1）
        # self.highFq_dict, self.cuckoo_tuple = self.read_dict_file2(coor_dir + '2')
        # import sys
        # from pympler import asizeof
        # print(sys.getsizeof(self.cuckoo_key), sys.getsizeof(self.cuckoo_value), sys.getsizeof(self.highFq_dict))
        # print(asizeof.asizeof(self.cuckoo_key), asizeof.asizeof(self.cuckoo_value), asizeof.asizeof(self.highFq_dict))
        two_pow_l1, two_pow_l2sub2 = 1 << l1, 1 << l2 - 2  # 2^l1, 2^(l2-2)
        if not hash_dir or not coor_dir:  # 有字典文件不存在
            need = hash_dir_try + '/' + coor_dir_try if not hash_dir and not coor_dir \
                else (hash_dir_try if coor_dir else coor_dir_try)
            print('字典文件%s不存在，正在生成...（预计耗时%dmin）' % (need, 2**(l1 - 20) * 1.5))
            time_1 = time.perf_counter()
            hash_list, coor_list = [0] * (two_pow_l1 + 1), [0] * (two_pow_l1 + 1)  # 当m=1~2^l1时，g^m对应的hash字节串和FQ列表
            gm, g2, key_num, two_pow_l1_div256_sub1 = self.ge, self.ge.GT_sqr(), 0, (two_pow_l1 >> 8) - 1
            for i in range(1, two_pow_l1, 2):  # 迭代>=1的奇数
                m, t = i, gm
                while True:  # 遍历有奇数因子i的偶数
                    if not hash_dir:
                        hash_list[m] = sm3(to_byte(t))
                    if not coor_dir:
                        coor_list[m] = to_byte(t[0][0][0] % q, N_SIZE)  # [0][0][0]是最低位，[2][1][1]是最高位
                    key_num, m = key_num + 1, m << 1
                    if key_num & two_pow_l1_div256_sub1 == 0:  # 每完成1/256触发
                        print('已完成%d/256，耗时：%.2f s' % (key_num >> l1 - 8, time.perf_counter() - time_1))
                    if m > two_pow_l1:  # m>2^l1
                        break
                    t = t.GT_sqr()  # 用g^m的平方生成g^2m
                if i + 2 < two_pow_l1:
                    gm = gm * g2
            if not hash_dir:
                self.hash_dict = self.write_dict_file(hash_list, hash_dir_try)
            if not coor_dir:
                self.lowFq_dict = self.write_dict_file(coor_list, coor_dir_try)  # T1
        self.g_2_l1 = (self.ge ** two_pow_l1).frobenius6()
        self.g_2_l1add1 = self.g_2_l1.GT_sqr()
        self.mask_key = (1 << (self.key_size << 3)) - 1  # 用于从较长的大数中快速截断出key所在的低位
        time_T2, print_threshold = 2 ** (l2 - 14) * 0.3, 10  # 生成T2预计耗时和显示耗时进度的门槛/s
        print('正在生成T2（预计耗时%ds）' % time_T2)
        time_1 = time.perf_counter()
        self.T2 = [0] * (two_pow_l2sub2 + 1)
        gm, g2, cal_num, two_pow_l2sub6_sub1 = self.g_2_l1add1, self.g_2_l1add1.GT_sqr(), 0, (two_pow_l2sub2 >> 4) - 1
        for i in range(1, two_pow_l2sub2, 2):  # 迭代>=1的奇数
            m, t = i, gm
            while True:  # 遍历有奇数因子i的偶数
                self.T2[m], cal_num, m = t.get_fp_list(), cal_num + 1, m << 1
                if time_T2 > print_threshold and cal_num & two_pow_l2sub6_sub1 == 0:  # 每完成1/16触发
                    print('已完成%d/16，耗时：%.2f s' % (cal_num >> l2 - 6, time.perf_counter() - time_1))
                if m > two_pow_l2sub2:  # m>2^(l2-2)
                    break
                t = t.GT_sqr()  # 用g^m的平方生成g^2m
            if i + 2 < two_pow_l2sub2:
                gm = gm * g2
        print('生成T2完毕，耗时：%.2f s' % (time.perf_counter() - time_1))

    def read_dict_file(self, dict_file, int_key=False):
        print('读取字典文件：%s（预计耗时%ds）' % (dict_file, 2**(self.l1 - 24) * self.key_size * (1.5 if int_key else 1.3)))
        time_1 = time.perf_counter()
        with open(dict_file, 'rb') as f:  # 读取字典文件
            data = f.read()
        m_dict, m = {}, 1
        if int_key:  # 键为整数
            for i in range(0, self.key_size << self.l1, self.key_size):
                m_dict[to_int(data[i:i + self.key_size])], m = m, m + 1
        else:
            for i in range(0, self.key_size << self.l1, self.key_size):
                m_dict[data[i:i + self.key_size]], m = m, m + 1
        print('耗时：%.2f s' % (time.perf_counter() - time_1))
        return m_dict

    def read_dict_file2(self, dict_file):  # 生成cuckoo hash
        import sys
        sys.setrecursionlimit(3000)
        self.mask_idx = (1 << self.l1 + 2) - 1

        def cuckoo_kick(idx, key, m):
            if cuckoo_value[idx]:  # 该索引位被占用，递归踢出
                kick_m = cuckoo_value[idx]
                kick_i = (kick_m - 1) * self.key_size
                kick_key = to_int(data[kick_i:kick_i + self.key_size])
                kick_idx1, kick_key1 = kick_key & self.mask_idx, kick_key >> 32
                kick_idx2, kick_key2 = kick_key1 & self.mask_idx, kick_key & MASK_32
                kick_idx, kick_key = (kick_idx1, kick_key1) if idx == kick_idx2 else (kick_idx2, kick_key2)
                cuckoo_kick(kick_idx, kick_key, kick_m)
            cuckoo_key[idx], cuckoo_value[idx] = key, m
        print('读取字典文件%s，构造cuckoo哈希表（预计耗时%ds）' % (dict_file, 2**(self.l1 - 24) * self.key_size * 3.5))
        time_1 = time.perf_counter()
        with open(dict_file, 'rb') as f:  # 读取字典文件
            data = f.read()
        m_dict = {}
        import array
        cuckoo_key, cuckoo_value = [array.array('I', [0]) * (self.mask_idx + 1) for _ in range(2)]
        for i in range(0, self.key_size << self.l1, self.key_size):
            key, m = to_int(data[i:i + self.key_size]), i // self.key_size + 1
            m_dict[key] = m
            idx1, key1 = key & self.mask_idx, key >> 32
            if not cuckoo_value[idx1]:  # 第一索引位为空
                cuckoo_key[idx1], cuckoo_value[idx1] = key1, m
            else:  # 占用第二索引位
                idx2, key2 = key1 & self.mask_idx, key & MASK_32
                cuckoo_kick(idx2, key2, m)
        print('耗时：%.2f s' % (time.perf_counter() - time_1))
        return m_dict, (cuckoo_key, cuckoo_value)

    def write_dict_file(self, key_list, bin_dir):
        print('进行碰撞检测并写入文件（预计耗时%ds）' % (2**(self.l1 - 23) * self.key_size * 1.1))
        start = self.hash_start if 'hash' in bin_dir else self.coor_start  # 判断bytes类型
        time_1 = time.perf_counter()
        f_bin, save_whole, range_end, m_dict = bytearray(), False, (1 << self.l1) + 1, {}
        for m in range(1, range_end):
            key_byte = key_list[m][start:start + self.key_size]
            if key_byte in m_dict:
                print('key碰撞：%s, m1=%d, m2=%d' % (key_byte.hex().swapcase(), m_dict[key_byte], m))
                print('键的字节数：%d\t\t起始位置：%d' % (self.key_size, start))
                save_whole = True
                break
            m_dict[key_byte] = m
            f_bin.extend(key_byte)
        if save_whole:  # 若发生碰撞，则保存完整的m=1~2^l1对应的hash字节串，以便后续调整键的字节数或起始位置
            tmp_dir = bin_dir[:bin_dir.rfind('_')] + '_tmp'
            with open(tmp_dir, 'wb') as f:
                f.write(to_byte([key_list[m] for m in range(1, range_end)]))
            print('写入临时文件%s，耗时：%.2f s' % (tmp_dir, (time.perf_counter() - time_1)))
        else:
            with open(bin_dir, 'wb') as f:  # 将预计算表写入二进制文件
                f.write(f_bin)
            print('写入字典文件%s，耗时：%.2f s' % (bin_dir, (time.perf_counter() - time_1)))
        return m_dict

    def enc(self, IDB, m, r=None):  # 本文加密
        r = r if r else randrange(1, N)
        r_m = (r + m) % N
        c1 = fast_kG(H(1, to_byte(IDB) + self.hid_e_byte) * r_m % N, _kP1) + fast_kG(r_m, self.k_Pe_list)
        c2 = self.ge_pow(r)
        return c1, c2

    def dec(self, C, DLP=1):  # 本文解密
        c1, c2 = C
        if not c1.is_on_curve():
            return -1
        w_ = self.e_de(c1)
        gm = w_ * c2.frobenius6()
        if DLP == 1:
            return self.m_value(gm)
        if DLP == 2:
            return self.m_value2(gm)
        if DLP == 3:
            return self.m_value3(gm)
        if DLP == 4:
            return self.m_value4(gm)

    def homo_add(self, C_list):  # 同态加法
        c1, c2 = C_list[0]
        for c1i, c2i in C_list[1:]:
            c1, c2 = c1 + c1i, c2 * c2i
        return c1, c2

    def enc2(self, IDB, m, r=None):  # 文献[1]加密
        r = r if r else randrange(1, N)
        c1 = fast_kG(H(1, to_byte(IDB) + self.hid_e_byte) * r % N, _kP1) + fast_kG(r, self.k_Pe_list)
        w = self.ge_pow(r)
        c2 = self.ge ** (m % N) * w
        return c1, c2

    def dec2(self, C, DLP=2):  # 文献[1]解密
        c1, c2 = C
        if not c1.is_on_curve():
            return -1
        w_ = self.e_de(c1)
        gm = c2 * w_.frobenius6()
        if DLP == 1:
            return self.m_value(gm)
        if DLP == 2:
            return self.m_value2(gm)
        if DLP == 3:
            return self.m_value3(gm)
        if DLP == 4:
            return self.m_value4(gm)

    # def m_value_2(self, gm):  # 本文消息恢复算法
    #     t = gm
    #     for i in range(1 << self.l2 - 1):
    #         value = self.hash_dict.get(sm3(to_byte(t))[self.hash_start:self.hash_start + self.key_size], 0)
    #         if value:  # g^m / g^(i*2^(l1+1)) = g^value
    #             return (i << self.l1 + 1) + value
    #         t = t * self.g_2_l1add1
    #         value = self.hash_dict.get(sm3(to_byte(t.frobenius6()))[self.hash_start:self.hash_start + self.key_size], 0)
    #         if value:  # 1/(g^m / g^(i*2^(l1+1))) = g^value
    #             return (i + 1 << self.l1 + 1) - value
    #     return False
    #
    # def m_value2_2(self, gm):  # 文献[1]消息恢复算法
    #     t = gm
    #     for i in range(1 << self.l2):
    #         value = self.hash_dict.get(sm3(to_byte(t))[self.hash_start:self.hash_start + self.key_size], 0)
    #         if value:  # g^m / g^(i*2^l1) = g^value
    #             return (i << self.l1) + value
    #         t = t * self.g_2_l1
    #     return False

    def m_value(self, gm):  # 本文消息恢复算法
        t = gm
        for i in range(1 << self.l2 - 1):
            value = self.lowFq_dict.get(t[0][0][0] % q & self.mask_key, 0)
            if value and self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^m / g^(i*2^(l1+1)) = g^value
                return (i << self.l1 + 1) + value
            t = t * self.g_2_l1add1
            value = self.lowFq_dict.get(t.frobenius6()[0][0][0] % q & self.mask_key, 0)
            if value and self.ge_pow((i + 1 << self.l1 + 1) - value) == gm:  # 1/(g^m / g^(i*2^(l1+1))) = g^value
                return (i + 1 << self.l1 + 1) - value
        return False

    def m_value2(self, gm):  # 文献[1]消息恢复算法（BSGS）
        t = gm
        for i in range(1 << self.l2):
            value = self.lowFq_dict.get(t[0][0][0] % q & self.mask_key, 0)
            if value and self.ge_pow((i << self.l1) + value) == gm:  # g^m / g^(i*2^l1) = g^value
                return (i << self.l1) + value
            t = t * self.g_2_l1
        return False

    def m_value3(self, gm):  # FastGTDLP-sym（用最低位比对，正负值相同，每轮2次查表，最多验证2次，m为5B时更快）
        a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = gm.get_fp_list()  # 11是高位
        value = self.lowFq_dict.get(a0 & self.mask_key, 0)
        if value:  # g^|m| = g^value, m∈[-2^l1,2^l1]/{0}
            if self.ge_pow(value) == gm:  # g^m = g^value, m∈[1,2^l1]
                return value
            if self.ge_pow(N - value) == gm:  # g^-m = g^value, m∈[-2^l1,-1]
                return -value
        for i in range(1, len(self.T2)):
            b11, b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0 = self.T2[i]
            nochange = a0 * b0 - (a1 * b1 + a8 * b7 + a9 * b6 + a6 * b9 + a7 * b8 << 1)
            change = a2 * b3 + a3 * b2 + a4 * b11 + a5 * b10 + a10 * b5 + a11 * b4 << 1
            c0 = (nochange - change) % q  # c = a * b
            value = self.lowFq_dict.get(c0 & self.mask_key, 0)
            if value:  # g^|m-(i*2^(l1+1))| = g^value, m∈[2^l1+1,2^(l-1)]
                if self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^(m-(i*2^(l1+1))) = g^value
                    return (i << self.l1 + 1) + value
                if self.ge_pow((i << self.l1 + 1) - value) == gm:  # g^-(m-(i*2^(l1+1))) = g^value
                    return (i << self.l1 + 1) - value
            c0 = (nochange + change) % q  # c = a / b
            value = self.lowFq_dict.get(c0 & self.mask_key, 0)
            if value:  # g^|m+(i*2^(l1+1))| = g^value, m∈[-2^(l-1)+1,-2^l1-1]
                if self.ge_pow(N - (i << self.l1 + 1) + value) == gm:  # g^(m+(i*2^(l1+1))) = g^value
                    return -(i << self.l1 + 1) + value
                if self.ge_pow(N - (i << self.l1 + 1) - value) == gm:  # g^-(m+(i*2^(l1+1))) = g^value
                    return -(i << self.l1 + 1) - value
        return False

    # def m_value4(self, gm):  # 改进的消息恢复算法2
    #     a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = gm.get_fp_list()  # 11是高位
    #     value = self.highFq_dict.get(to_byte(a11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #     if value and self.ge_pow(value) == gm:  # g^m = g^value, m∈[1,2^l1]
    #         return value
    #     value = self.highFq_dict.get(to_byte(q - a11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #     if value and self.ge_pow(N - value) == gm:  # g^-m = g^value, m∈[-2^l1,-1]
    #         return -value
    #     for i in range(1, len(self.T2)):
    #         b11, b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0 = self.T2[i]
    #         nochange = a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a10 * b1 + a11 * b0
    #         change = a0 * b11 + a1 * b10 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2
    #         c11 = (nochange + change) % q  # c = a * b
    #         value = self.highFq_dict.get(to_byte(c11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #         if value and self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^(m-(i*2^(l1+1))) = g^value
    #             return (i << self.l1 + 1) + value
    #         value = self.highFq_dict.get(to_byte(q - c11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #         if value and self.ge_pow((i << self.l1 + 1) - value) == gm:  # g^-(m-(i*2^(l1+1))) = g^value
    #             return (i << self.l1 + 1) - value
    #         c11 = (nochange - change) % q  # c = a / b
    #         value = self.highFq_dict.get(to_byte(c11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #         if value and self.ge_pow(N - (i << self.l1 + 1) + value) == gm:  # g^(m+(i*2^(l1+1))) = g^value
    #             return -(i << self.l1 + 1) + value
    #         value = self.highFq_dict.get(to_byte(q - c11, N_SIZE)[self.coor_start:self.coor_start + self.key_size], 0)
    #         if value and self.ge_pow(N - (i << self.l1 + 1) - value) == gm:  # g^-(m+(i*2^(l1+1))) = g^value
    #             return -(i << self.l1 + 1) - value
    #     return False

    def m_value4(self, gm):  # FastGTDLP-asym（用最高位比对，正负值相反，每轮4次查表，最多验证1次，m为4B时更快）
        a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = gm.get_fp_list()  # 11是高位
        value = self.highFq_dict.get(a11 & self.mask_key, 0)
        if value and self.ge_pow(value) == gm:  # g^m = g^value, m∈[1,2^l1]
            return value
        value = self.highFq_dict.get(q - a11 & self.mask_key, 0)
        if value and self.ge_pow(N - value) == gm:  # g^-m = g^value, m∈[-2^l1,-1]
            return -value
        for i in range(1, len(self.T2)):
            b11, b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0 = self.T2[i]
            nochange = a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a10 * b1 + a11 * b0
            change = a0 * b11 + a1 * b10 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2
            c11 = (nochange + change) % q  # c = a * b
            value = self.highFq_dict.get(c11 & self.mask_key, 0)
            if value and self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^(m-(i*2^(l1+1))) = g^value
                return (i << self.l1 + 1) + value
            value = self.highFq_dict.get(q - c11 & self.mask_key, 0)
            if value and self.ge_pow((i << self.l1 + 1) - value) == gm:  # g^-(m-(i*2^(l1+1))) = g^value
                return (i << self.l1 + 1) - value
            c11 = (nochange - change) % q  # c = a / b
            value = self.highFq_dict.get(c11 & self.mask_key, 0)
            if value and self.ge_pow(N - (i << self.l1 + 1) + value) == gm:  # g^(m+(i*2^(l1+1))) = g^value
                return -(i << self.l1 + 1) + value
            value = self.highFq_dict.get(q - c11 & self.mask_key, 0)
            if value and self.ge_pow(N - (i << self.l1 + 1) - value) == gm:  # g^-(m+(i*2^(l1+1))) = g^value
                return -(i << self.l1 + 1) - value
        return False
    
    # def m_value5(self, gm):  # cuckoo hash，内存占用约为普通字典的28%，速度略慢
    #     def cuckoo_lookup(key):
    #         idx1, key1 = key & mask_idx, key >> 32  # 计算第一索引和校对键
    #         if cuckoo_key[idx1] == key1:  # 第一索引位匹配
    #             return cuckoo_value[idx1]
    #         idx2, key2 = key1 & mask_idx, key & MASK_32  # 计算第二索引和校对键
    #         if cuckoo_key[idx2] == key2:  # 第二索引位匹配
    #             return cuckoo_value[idx2]
    #         return 0
    #
    #     cuckoo_key, cuckoo_value = self.cuckoo_tuple
    #     mask_idx, mask_key = self.mask_idx, self.mask_key
    #     a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = gm.get_fp_list()  # 11是高位
    #     value = cuckoo_lookup(a11 & mask_key)
    #     if value and self.ge_pow(value) == gm:  # g^m = g^value, m∈[1,2^l1]
    #         return value
    #     value = cuckoo_lookup(q - a11 & mask_key)
    #     if value and self.ge_pow(N - value) == gm:  # g^-m = g^value, m∈[-2^l1,-1]
    #         return -value
    #     for i in range(1, len(self.T2)):
    #         b11, b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0 = self.T2[i]
    #         nochange = a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a10 * b1 + a11 * b0
    #         change = a0 * b11 + a1 * b10 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2
    #         c11 = (nochange + change) % q  # c = a * b
    #         value = cuckoo_lookup(c11 & mask_key)
    #         if value and self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^(m-(i*2^(l1+1))) = g^value
    #             return (i << self.l1 + 1) + value
    #         value = cuckoo_lookup(q - c11 & mask_key)
    #         if value and self.ge_pow((i << self.l1 + 1) - value) == gm:  # g^-(m-(i*2^(l1+1))) = g^value
    #             return (i << self.l1 + 1) - value
    #         c11 = (nochange - change) % q  # c = a / b
    #         value = cuckoo_lookup(c11 & mask_key)
    #         if value and self.ge_pow(N - (i << self.l1 + 1) + value) == gm:  # g^(m+(i*2^(l1+1))) = g^value
    #             return -(i << self.l1 + 1) + value
    #         value = cuckoo_lookup(q - c11 & mask_key)
    #         if value and self.ge_pow(N - (i << self.l1 + 1) - value) == gm:  # g^-(m+(i*2^(l1+1))) = g^value
    #             return -(i << self.l1 + 1) - value
    #     return False

    # def m_value6(self, gm):  # 多线程，Python有GIL，发挥不出；多进程运行不了
    #     a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = gm.get_fp_list()  # 11是高位
    #     mask_key = (1 << (self.key_size << 3)) - 1  # 用于从较长的大数中快速截断出key所在的低位
    #     value = self.m_dict4.get(a11 & mask_key, 0)
    #     if value and self.ge_pow(value) == gm:  # g^m = g^value, m∈[1,2^l1]
    #         return value
    #     value = self.m_dict4.get(q - a11 & mask_key, 0)
    #     if value and self.ge_pow(N - value) == gm:  # g^-m = g^value, m∈[-2^l1,-1]
    #         return -value
    #
    #     self.gm, self.mask_key = gm, mask_key
    #     self.a = a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0
    #     for i in range(1, len(self.T2), 4):
    #         # with ThreadPoolExecutor() as executor:
    #         #     results = list(executor.map(self.check_T2, range(i, i+4)))
    #         # pool = multiprocessing.Pool(2)
    #         # results = pool.map(self.check_T2, range(i, i+2))
    #         # pool.close()
    #         # pool.join()
    #         for result in results:
    #             if result is not None:
    #                 return result
    #
    #     return False
    #
    # def check_T2(self, i):
    #     a11, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 = self.a
    #     gm, mask_key = self.gm, self.mask_key
    #     b11, b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0 = self.T2[i]
    #     nochange = a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a10 * b1 + a11 * b0
    #     change = a0 * b11 + a1 * b10 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2
    #     c11 = (nochange + change) % q  # c = a * b
    #     value = self.m_dict4.get(c11 & mask_key, 0)
    #     if value and self.ge_pow((i << self.l1 + 1) + value) == gm:  # g^(m-(i*2^(l1+1))) = g^value
    #         return (i << self.l1 + 1) + value
    #     value = self.m_dict4.get(q - c11 & mask_key, 0)
    #     if value and self.ge_pow((i << self.l1 + 1) - value) == gm:  # g^-(m-(i*2^(l1+1))) = g^value
    #         return (i << self.l1 + 1) - value
    #     c11 = (nochange - change) % q  # c = a / b
    #     value = self.m_dict4.get(c11 & mask_key, 0)
    #     if value and self.ge_pow(N - (i << self.l1 + 1) + value) == gm:  # g^(m+(i*2^(l1+1))) = g^value
    #         return -(i << self.l1 + 1) + value
    #     value = self.m_dict4.get(q - c11 & mask_key, 0)
    #     if value and self.ge_pow(N - (i << self.l1 + 1) - value) == gm:  # g^-(m+(i*2^(l1+1))) = g^value
    #         return -(i << self.l1 + 1) - value


from cProfile import Profile
prof = Profile()
def sm9_prof_test():
    def prof_func():
        # z_list = [0 for _ in range(n)]
        # for i in range(n):
        #     cal_z_list(h_list[i], 0, h_list[i + 1:], z_list)
        # z_list = [z % N for z in z_list]
        t_list = cal_z_list2(h_list)

    n = 1600
    h_list = [randrange(1, N) for _ in range(n)]
    # IDB = 'BILL456@YAHOO.COM'
    # kgc = SM9(ke=0x01EDEE3778F441F8DEA3D9FA0ACC4E07EE36C93F9A08618AF4AD85CEDE1C22)
    # sm9 = kgc.KGC_gen_user(IDB)
    # a = b = sm9.ge
    prof.runcall(prof_func)
    prof.print_stats(1)


# 输入单个消息位数和数量列表
def test_GTDLP(bit_num_list, num_list):
    IDB = 'BILL456@YAHOO.COM'
    kgc = SM9(ke=0x01EDEE3778F441F8DEA3D9FA0ACC4E07EE36C93F9A08618AF4AD85CEDE1C22)
    sm9_B = SM9_HOMO(kgc.KGC_gen_user(IDB), l2=max(bit_num_list)-24)
    for bit_num, m_num in zip(bit_num_list, num_list):
        print('\n----------------GTDLP（位数：%d，数量：%d）----------------' % (bit_num, m_num))
        m_max = 1 << bit_num
        m_list = [randrange(1, m_max) for _ in range(m_num)]
        time_0 = time.perf_counter()
        gm_list = [sm9_B.ge_pow(m) for m in m_list]
        m_max_half = m_max >> 1
        gm_neg = sm9_B.ge_pow(m_max_half).frobenius6()
        gm_list2 = [gm * gm_neg for gm in gm_list]  # 将m从[1,2^l]映射到[-2^(l-1)+1,2^(l-1)]
        print('生成g^m，耗时%.2f ms' % ((time.perf_counter() - time_0) * 1000))
        res1, res2, res3, res4 = [], [], [], []
        time_1 = time.perf_counter()
        # BSGS
        for gm in gm_list:
            res1.append(sm9_B.m_value2(gm))
        time_2 = time.perf_counter()
        # # 本文
        # for gm in gm_list:
        #     res2.append(sm9_B.m_value(gm))
        time_3 = time.perf_counter()
        # FastGTDLP-sym
        for gm in gm_list2:
            res3.append(sm9_B.m_value3(gm))
        time_4 = time.perf_counter()
        # FastGTDLP-asym
        for gm in gm_list2:
            res4.append(sm9_B.m_value4(gm))
        time_5 = time.perf_counter()
        time_relative = time_2 - time_1
        print('BSGS\t\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / m_num, time_relative / (time_2 - time_1)))
        # print('本文\t\t耗时%.2f ms  \t相对速率%.2f' % ((time_3 - time_2) * 1000 / m_num, time_relative / (time_3 - time_2)))
        print('FastGTDLP-sym\t耗时%.2f ms  \t相对速率%.2f' % ((time_4 - time_3) * 1000 / m_num, time_relative / (time_4 - time_3)))
        print('FastGTDLP-asym\t耗时%.2f ms  \t相对速率%.2f' % ((time_5 - time_4) * 1000 / m_num, time_relative / (time_5 - time_4)))
        res3, res4 = [res + m_max_half for res in res3], [res + m_max_half for res in res4]
        assert m_list == res1 == res3 == res4


# 输入单个消息位数和数量列表
def test_AHE_GTDLP(bit_num_list, num_list):
    IDB = 'BILL456@YAHOO.COM'
    kgc = SM9(ke=0x01EDEE3778F441F8DEA3D9FA0ACC4E07EE36C93F9A08618AF4AD85CEDE1C22)
    sm9_B = SM9_HOMO(kgc.KGC_gen_user(IDB), l2=max(bit_num_list)-24)
    for bit_num, m_num in zip(bit_num_list, num_list):
        print('\n----------------ID-AHE+GTDLP（位数：%d，数量：%d）----------------' % (bit_num, m_num))
        m_max = 1 << bit_num
        m_max_half = m_max >> 1
        m_list = [randrange(1, m_max) for _ in range(m_num)]
        m_list2 = [m - m_max_half for m in m_list]
        print('---------------------------加密---------------------------')
        enc1_data, enc1_data2, enc2_data, enc2_data2 = [], [], [], []
        time_1 = time.perf_counter()
        # 本文
        for m in m_list:
            enc1_data.append(sm9_B.enc(IDB, m))
        for m in m_list2:
            enc1_data2.append(sm9_B.enc(IDB, m))
        time_2 = time.perf_counter()
        # 文献[1]
        for m in m_list:
            enc2_data.append(sm9_B.enc2(IDB, m))
        for m in m_list2:
            enc2_data2.append(sm9_B.enc2(IDB, m))
        time_3 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms  \t相对耗时%.2f' % ((time_2 - time_1) * 500 / m_num, (time_2 - time_1) / time_relative))
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 500 / m_num, (time_3 - time_2) / time_relative))

        # print('\n---------------------------本文解密---------------------------')
        # res1, res2, res3 = [], [], []
        # time_1 = time.perf_counter()
        # # BSGS
        # for C in enc1_data:
        #     res1.append(sm9_B.dec(C, 2))
        # time_2 = time.perf_counter()
        # # FastGTDLP-sym
        # for C in enc1_data2:
        #     res2.append(sm9_B.dec(C, 3))
        # time_3 = time.perf_counter()
        # # FastGTDLP-asym
        # for C in enc1_data2:
        #     res3.append(sm9_B.dec(C, 4))
        # time_4 = time.perf_counter()
        # time_relative = time_2 - time_1
        # print('BSGS\t\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / m_num, time_relative / (time_2 - time_1)))
        # print('FastGTDLP-sym\t耗时%.2f ms  \t相对速率%.2f' % ((time_3 - time_2) * 1000 / m_num, time_relative / (time_3 - time_2)))
        # print('FastGTDLP-asym\t耗时%.2f ms  \t相对速率%.2f' % ((time_4 - time_3) * 1000 / m_num, time_relative / (time_4 - time_3)))
        # res2, res3 = [res + m_max_half for res in res2], [res + m_max_half for res in res3]
        # assert m_list == res1 == res2 == res3

        print('\n---------------------------文献[1]解密---------------------------')
        res1, res2, res3 = [], [], []
        time_1 = time.perf_counter()
        # BSGS
        for C in enc2_data:
            res1.append(sm9_B.dec2(C, 2))
        time_2 = time.perf_counter()
        # FastGTDLP-sym
        for C in enc2_data2:
            res2.append(sm9_B.dec2(C, 3))
        time_3 = time.perf_counter()
        # FastGTDLP-asym
        for C in enc2_data2:
            res3.append(sm9_B.dec2(C, 4))
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('BSGS\t\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / m_num, time_relative / (time_2 - time_1)))
        print('FastGTDLP-sym\t耗时%.2f ms  \t相对速率%.2f' % ((time_3 - time_2) * 1000 / m_num, time_relative / (time_3 - time_2)))
        print('FastGTDLP-asym\t耗时%.2f ms  \t相对速率%.2f' % ((time_4 - time_3) * 1000 / m_num, time_relative / (time_4 - time_3)))
        res2, res3 = [res + m_max_half for res in res2], [res + m_max_half for res in res3]
        assert m_list == res1 == res2 == res3


# 输入单个消息数量、同态加法的消息数列表、同态加法的测试次数列表
def test_homo(m_num, homo_m_num, homo_test_num):
    IDB = 'BILL456@YAHOO.COM'
    kgc = SM9(ke=0x01EDEE3778F441F8DEA3D9FA0ACC4E07EE36C93F9A08618AF4AD85CEDE1C22)
    sm9_B = SM9_HOMO(kgc.KGC_gen_user(IDB))
    m_list = [randrange(1, 4294967296) for _ in range(m_num)]
    print('---------------------------加密---------------------------')
    enc1_data, enc2_data = [], []
    time_1 = time.perf_counter()
    # 本文
    for m in m_list:
        enc1_data.append(sm9_B.enc(IDB, m))
    time_2 = time.perf_counter()
    # 文献[1]
    for m in m_list:
        enc2_data.append(sm9_B.enc2(IDB, m))
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / m_num, (time_2 - time_1) / time_relative))
    print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / m_num, (time_3 - time_2) / time_relative))

    print('\n---------------------------解密---------------------------')
    res1, res2, res3 = [], [], []
    time_1 = time.perf_counter()
    # 本文
    for C in enc1_data:
        res1.append(sm9_B.dec(C))
    time_2 = time.perf_counter()
    # 文献[1]
    for C in enc2_data:
        res2.append(sm9_B.dec2(C))
    time_3 = time.perf_counter()
    # 改进的消息恢复算法
    for C in enc1_data:
        res3.append(sm9_B.dec(C, True))
    time_4 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / m_num, (time_2 - time_1) / time_relative))
    print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / m_num, (time_3 - time_2) / time_relative))
    print('改进DLP\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / m_num, (time_4 - time_3) / time_relative))
    assert m_list == res1 == res2 == res3

    for msg_num, test_num in zip(homo_m_num, homo_test_num):
        print('\n----------------同态加法（%d个消息，测试%d次）----------------' % (msg_num, test_num))
        sample_lists = [sample(range(m_num), msg_num) for _ in range(test_num)]
        enc1_lists = [[enc1_data[i] for i in sample_list] for sample_list in sample_lists]
        enc2_lists = [[enc2_data[i] for i in sample_list] for sample_list in sample_lists]
        enc1_homo, enc2_homo = [], []
        time_1 = time.perf_counter()
        # 本文
        for enc_list in enc1_lists:
            enc1_homo.append(sm9_B.homo_add(enc_list))
        time_2 = time.perf_counter()
        # 文献[1]
        for enc_list in enc2_lists:
            enc2_homo.append(sm9_B.homo_add(enc_list))
        time_3 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

        print('\n-----------------同态加法后的解密（%d个消息）-----------------' % msg_num)
        res1, res2, res3 = [], [], []
        time_1 = time.perf_counter()
        # 本文
        for C in enc1_homo:
            res1.append(sm9_B.dec(C))
        time_2 = time.perf_counter()
        # 文献[1]
        for C in enc2_homo:
            res2.append(sm9_B.dec2(C))
        time_3 = time.perf_counter()
        # 改进的消息恢复算法
        for C in enc1_homo:
            res3.append(sm9_B.dec(C, True))
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('改进DLP\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
        assert [sum(m_list[i] for i in sample_list) for sample_list in sample_lists] == res1 == res2 == res3


# ————————————————————————————————————论文—基于国密算法SM9的环签名方案—实验代码————————————————————————————————————
# ————————————————————————————————————论文—基于SM9的环签名：常数级计算开销的方案构造—实验代码————————————————————————————————————
# 文献[1]：彭聪, 何德彪, 罗敏, 等. 基于SM9标识密码算法的环签名方案[J]. 密码学报, 2021, 8(4): 724-734
# 文献[2]：饶金涛, 崔喆. 基于SM9盲签名与环签名的安全电子选举协议[J]. 计算机工程, 2023, 49(6): 13-23, 33
class SM9_RING(SM9):
    def __init__(self, sm9):
        self.ID, self.ID_byte, self.Ppub_s, self.gs = sm9.ID, sm9.ID_byte, sm9.Ppub_s, sm9.gs
        self.k_ds_list, self.gs_comb_list, self.hid_s_byte = sm9.k_ds_list, sm9.gs_comb_list, sm9.hid_s_byte
        # self.T = e(fast_kG(1, self.k_ds_list), self.Ppub_s)  # 文献[2]
        ds = self.k_ds_list[0][1]
        self.g1_comb_list, self.g2_comb_list = get_comb_list(e(ds, P2)), get_comb_list(e(ds, self.Ppub_s))
        self.k_Ps_list = get_kP_list(self.Ppub_s)

    # 本文（基于国密算法SM9的环签名方案）
    def sign0(self, M, ID_list, pi=None, r_list=None):
        n = len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        ID_list = [to_byte(ID) for ID in ID_list]
        Un_M_byte = to_byte(ID_list) + to_byte(M)
        r_list, h_list = r_list if r_list else [randrange(1, N) for _ in range(n + 1)], [0] * n
        r, r0 = r_list.pop(0), r_list[pi]
        r_r0 = r * r0 % N
        w_pi_add_1 = self.gs_pow(r_r0)
        i = (pi + 1) % n
        h_list[i] = H(2, Un_M_byte + to_byte(w_pi_add_1))  # h_π+1
        for _ in range(n - 1):
            vi, r_ri = H(1, ID_list[i] + self.hid_s_byte), r * r_list[i] % N
            ui = comb_pow(r_ri * vi % N, self.g1_comb_list) * comb_pow(r_ri, self.g2_comb_list)
            w_i_add_1 = ui * self.gs_pow(h_list[i])
            i = (i + 1) % n
            h_list[i] = H(2, Un_M_byte + to_byte(w_i_add_1))  # h_i+1
        S = fast_kG(r, self.k_ds_list)
        r_list[pi] = (r_r0 - h_list[pi]) * mod_inv(r, N) % N
        return h_list[0], S, r_list

    def verify0(self, M, ID_list, h, S, r_list):
        for t in [h] + r_list:
            if not 0 < t < N:
                return False
        if not S.is_on_curve():
            return False
        ID_list = [to_byte(ID) for ID in ID_list]
        n, Un_M_byte, hi = len(ID_list), to_byte(ID_list) + to_byte(M), h
        # if n > 7:  # 当n>7时预计算才更快
        g3_comb_list, g4_comb_list = get_comb_list(e(S, P2)), get_comb_list(e(S, self.Ppub_s))
        for i in range(n):
            vi = H(1, ID_list[i] + self.hid_s_byte)
            ui = comb_pow(vi * r_list[i] % N, g3_comb_list) * comb_pow(r_list[i], g4_comb_list)
            w_i_add_1 = ui * self.gs_pow(hi)
            hi = H(2, Un_M_byte + to_byte(w_i_add_1))  # h_i+1
        # else:
        #     ui = e(S, fast_kG(vi, _kP2) + self.Ppub_s)
        return h == hi

    # 文献[1]
    def sign1(self, M, ID_list, pi=None, r_list=None):
        n = len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        ID_list = [to_byte(ID) for ID in ID_list]
        Un_M_byte = to_byte(ID_list) + to_byte(M)
        r_list, h_list, R_list = r_list if r_list else [randrange(1, N) for _ in range(n)], [0] * n, [0] * n
        r = r_list[pi]
        R = fast_kG(r, _kP1)
        w_pi_add_1 = e(R, self.Ppub_s)  # self.gs_pow(r)
        i = (pi + 1) % n
        h_list[i] = H(2, Un_M_byte + to_byte(w_pi_add_1))  # h_π+1
        for _ in range(n - 1):
            Ri = R_list[i] = fast_kG(r_list[i], _kP1)
            vi = H(1, ID_list[i] + self.hid_s_byte)
            ui = e(Ri, fast_kG(vi, _kP2) + self.Ppub_s)
            w_i_add_1 = ui * self.gs_pow(h_list[i])
            i = (i + 1) % n
            h_list[i] = H(2, Un_M_byte + to_byte(w_i_add_1))  # h_i+1
        l = (r - h_list[pi]) % N
        assert l != 0
        R_list[pi] = fast_kG(l, self.k_ds_list)
        return h_list[0], R_list

    def verify1(self, M, ID_list, h, R_list):
        if not 0 < h < N:
            return False
        for R in R_list:
            if not R.is_on_curve():
                return False
        ID_list = [to_byte(ID) for ID in ID_list]
        n, Un_M_byte, hi = len(ID_list), to_byte(ID_list) + to_byte(M), h
        for i in range(n):
            vi = H(1, ID_list[i] + self.hid_s_byte)
            ui = e(R_list[i], fast_kG(vi, _kP2) + self.Ppub_s)
            w_i_add_1 = ui * self.gs_pow(hi)
            hi = H(2, Un_M_byte + to_byte(w_i_add_1))  # h_i+1
        return h == hi

    # 文献[2]
    def sign2(self, M, ID_list, pi=None, r_list=None):
        pi = ID_list.index(self.ID) if pi is None else pi
        r_list = r_list if r_list else [randrange(1, N) for _ in range(len(ID_list))]
        v_list = [H(1, ID) for ID in ID_list]
        r, v_pi = r_list.pop(pi), v_list.pop(pi)
        R = fast_kG(r, _kP1)
        sum_viri_r = sum(vi * ri for vi, ri in zip(v_list, r_list)) * r % N
        W = e(R, self.Ppub_s) * e(P1, self.Ppub_s * sum_viri_r)  # self.gs_pow((r + sum_viri_r) % N)
        h = H(2, to_byte(ID_list) + to_byte(M) + to_byte(W))
        r_pi = (h - sum(r_list)) % N
        S = R - fast_kG(v_pi * r_pi * r % N, _kP1)  # fast_kG((1 - v_pi * r_pi) * r % N, _kP1)
        r_list.insert(pi, r_pi)
        return self.T, R, S, r_list

    def verify2(self, M, ID_list, T, R, S, r_list):
        if not R.is_on_curve() or not S.is_on_curve():
            return False
        v_list = [H(1, ID) for ID in ID_list]
        sum_viri = sum(vi * ri for vi, ri in zip(v_list, r_list)) % N
        W = e(S, self.Ppub_s) * e(R * sum_viri, self.Ppub_s)  # e(S + R * sum_viri, self.Ppub_s)
        h = H(2, to_byte(ID_list) + to_byte(M) + to_byte(W))
        return sum(r_list) == h

    # 本文（基于SM9的环签名：常数级计算开销的方案构造）
    def sign3(self, M, ID_list, pi=None, r_list=None):
        n = len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        r_list = r_list if r_list else [randrange(1, N) for _ in range(n + 2)]  # r0=r_list[pi],r=r_list[n],ρ=r_list[-1]
        r0, rho, r = r_list[pi], r_list.pop(), r_list.pop()
        r_r0 = r * r0 % N
        w = self.gs_pow(r_r0)
        ID_list = [to_byte(ID) for ID in ID_list]
        sum_rivi, sum_ri = 0, 0  # 不含序号π
        for i in [i for i in range(n) if i != pi]:
            sum_rivi, sum_ri = sum_rivi + r_list[i] * H(1, ID_list[i] + self.hid_s_byte), sum_ri + r_list[i]
        beta = comb_pow(N - sum_rivi * r % N, self.g1_comb_list) * comb_pow(N - sum_ri * r % N, self.g2_comb_list) \
                * self.gs_pow(N - rho * r % N)
        h = H(2, to_byte([ID_list, M, w, beta]))
        S = fast_kG(r, self.k_ds_list)
        r_list[pi] = ((r_r0 - h) * mod_inv(r, N) + rho) % N
        return h, S, beta, r_list

    def verify3(self, M_, ID_list, h_, S_, beta_, r_list):
        for t in [h_] + r_list:
            if not 0 < t < N:
                return False
        if not S_.is_on_curve():
            return False
        ID_list = [to_byte(ID) for ID in ID_list]
        sum_rivi, sum_ri = 0, 0
        for ri_, IDi in zip(r_list, ID_list):
            sum_rivi, sum_ri = sum_rivi + ri_ * H(1, IDi + self.hid_s_byte), sum_ri + ri_
        w_ = e(S_, fast_kG(sum_rivi % N, _kP2) + fast_kG(sum_ri % N, self.k_Ps_list)) * beta_ * self.gs_pow(h_)
        h2 = H(2, to_byte([ID_list, M_, w_, beta_]))
        return h_ == h2


# 基于国密算法SM9的环签名方案
# 输入环用户数量列表、测试次数列表
def test_ring(n_list, test_num_list):
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9(ks=0x01EDEE3778F441F8DEA3D9FA0ACC4E07EE36C93F9A08618AF4AD85CEDE1C22)
    sm9_A = SM9_RING(kgc.KGC_gen_user(IDA))
    raw_ID_list = [IDA + str(i) for i in range(max(n_list))]
    M_list = ['Ring signature test' + str(i) for i in range(max(test_num_list))]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------环签名（%d个环用户，测试%d次）----------------' % (n, test_num))
        ID_lists = [sample(raw_ID_list, n) for _ in range(test_num)]
        pi_list = [randrange(0, n) for _ in range(test_num)]
        for i in range(test_num):
            ID_lists[i][pi_list[i]] = IDA
        ring_sig1, ring_sig2 = [], []
        time_1 = time.perf_counter()
        # 本文
        for i in range(test_num):
            ring_sig1.append(sm9_A.sign0(M_list[i], ID_lists[i], pi_list[i]))
        time_2 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            ring_sig2.append(sm9_A.sign1(M_list[i], ID_lists[i], pi_list[i]))
        time_3 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

        print('\n---------------环签名验证（%d个环用户，测试%d次）--------------' % (n, test_num))
        res1, res2 = [], []
        time_1 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res1.append(sm9_A.verify0(M_list[i], ID_lists[i], *ring_sig1[i]))
        time_2 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res2.append(sm9_A.verify1(M_list[i], ID_lists[i], *ring_sig2[i]))
        time_3 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        assert all(res1) and all(res2)


# 基于SM9的环签名：常数级计算开销的方案构造
# 输入环用户数量列表、测试次数列表
# 文献[1]：彭聪, 何德彪, 罗敏, 等. 基于SM9标识密码算法的环签名方案[J]. 密码学报, 2021, 8(4): 724-734
# 文献[2]：谢振杰, 张耀, 杨启超, 等. 基于国密算法SM9的环签名方案[J/OL]．计算机科学
# 文献[3]：安浩杨, 何德彪, 包子健, 等. 基于SM9数字签名的环签名及其在区块链隐私保护中的应用[J]. 计算机研究与发展, 2023, 60(11): 2545-2554
# 文献[4]：谢振杰, 尹小康, 蔡瑞杰, 等. 基于国密算法SM9的可追踪环签名方案[J]. 通信学报, 2025, 46(3): 199-211
def test_ring2(n_list, test_num_list):
    IDA = 'ALICE123@YAHOO.COM'
    max_n, sm9_A = max(n_list), SM9(ks=-1).KGC_gen_user(IDA)
    sm9_ring = SM9_RING(sm9_A)
    sm9_accuring = SM9_ACCURING(sm9_A, max_n, True)
    raw_ID_list = [IDA + str(i) for i in range(max_n << 1)]
    M_list = ['Ring signature2 test' + str(i) for i in range(max(test_num_list))]
    time_data, time_data2 = [[] for _ in range(10)], [[] for _ in range(10)]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------环签名（%d个环用户，测试%d次）----------------' % (n, test_num))
        ID_lists = [sample(raw_ID_list, n) for _ in range(test_num)]
        pi_list = [randrange(0, n) for _ in range(test_num)]
        r_lists = [[randrange(1, N) for _ in range(max(10, n + 2))] for __ in range(test_num)]
        for i in range(test_num):
            ID_lists[i][pi_list[i]] = IDA
        ring_sig1, ring_sig2, ring_sig3, ring_sig4, ring_sig5 = [], [], [], [], []
        # sm9_accuring.pre_cal(ID_lists[0])
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            ring_sig1.append(sm9_ring.sign1(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:-2]))
        time_2 = time.perf_counter()
        # 文献[2]
        for i in range(test_num):
            ring_sig2.append(sm9_ring.sign0(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:-1]))
        time_3 = time.perf_counter()
        # 文献[3]
        for i in range(test_num):
            ring_sig3.append(sm9_accuring.sign1(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:10]))
        time_4 = time.perf_counter()
        # 文献[4]
        for i in range(test_num):
            ring_sig4.append(sm9_accuring.sign0(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:2]))
        time_5 = time.perf_counter()
        # 本文
        for i in range(test_num):
            ring_sig5.append(sm9_ring.sign3(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:]))
        time_6 = time.perf_counter()
        time_relative = time_6 - time_5
        print('文献[1]\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[2]\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('文献[3]\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
        print('文献[4]\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, (time_5 - time_4) / time_relative))
        print('本文\t\t耗时%.2f ms \t相对速率%.2f' % ((time_6 - time_5) * 1000 / test_num, (time_6 - time_5) / time_relative))
        j = 0
        for t1, t2 in zip([time_1, time_2, time_3, time_4, time_5], [time_2, time_3, time_4, time_5, time_6]):
            time_data[j].append('%.2f' % ((t2 - t1) * 1000 / test_num))
            time_data2[j].append('%.2f' % ((t2 - t1) / time_relative))
            j += 1

        print('\n---------------环签名验证（%d个环用户，测试%d次）--------------' % (n, test_num))
        res1, res2, res3, res4, res5 = [], [], [], [], []
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res1.append(sm9_ring.verify1(M_list[i], ID_lists[i], *ring_sig1[i]))
        time_2 = time.perf_counter()
        # 文献[2]
        for i in range(test_num):
            res2.append(sm9_ring.verify0(M_list[i], ID_lists[i], *ring_sig2[i]))
        time_3 = time.perf_counter()
        # 文献[3]
        for i in range(test_num):
            res3.append(sm9_accuring.verify1(M_list[i], ring_sig3[i], ID_lists[i]))
        time_4 = time.perf_counter()
        # 文献[4]
        for i in range(test_num):
            res4.append(sm9_accuring.verify0(M_list[i], *ring_sig4[i], ID_lists[i]))
        time_5 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res5.append(sm9_ring.verify3(M_list[i], ID_lists[i], *ring_sig5[i]))
        time_6 = time.perf_counter()
        time_relative = time_6 - time_5
        print('文献[1]\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[2]\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('文献[3]\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
        print('文献[4]\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, (time_5 - time_4) / time_relative))
        print('本文\t\t耗时%.2f ms \t相对速率%.2f' % ((time_6 - time_5) * 1000 / test_num, (time_6 - time_5) / time_relative))
        assert all(res1) and all(res2) and all(res3) and all(res4) and all(res5)
        for t1, t2 in zip([time_1, time_2, time_3, time_4, time_5], [time_2, time_3, time_4, time_5, time_6]):
            time_data[j].append('%.2f' % ((t2 - t1) * 1000 / test_num))
            time_data2[j].append('%.2f' % ((t2 - t1) / time_relative))
            j += 1
    print('')
    for line in time_data + time_data2:
        print('\t'.join(line))


# ————————————————————————————————————论文—基于国密算法SM9的签密方案—实验代码————————————————————————————————————
# 文献[1]：赖建昌, 黄欣沂, 何德彪, 等. 基于商密SM9的高效标识签密[J]. 密码学报, 2021, 8(2): 314-329
class SM9_SIGNENC(SM9):
    def __init__(self, sm9, ks):  # ks是签名私钥
        self.ID, self.ID_byte, self.Ppub_s, self.gs = sm9.ID, sm9.ID_byte, sm9.Ppub_s, sm9.gs
        self.k_ds_list, self.gs_comb_list, self.hid_s_byte = sm9.k_ds_list, sm9.gs_comb_list, sm9.hid_s_byte
        # 本文需要
        h1 = H(1, self.ID_byte + self.hid_s_byte)
        self.h1_inv, t2 = mod_inv(h1, N), ks * mod_inv(h1 + ks, N) % N
        self.k_de2_list, self.k_Ps_list = get_kP_list(fast_kG(ks * t2 % N, _kP2)), get_kP_list(self.Ppub_s)
        # 文献[1]需要
        self.de_a_list, self.Ppub_e = get_a_list(fast_kG(t2, _kP2)), fast_kG(ks, _kP1)

    # 本文
    def Signcrypt(self, M, IDB):
        IDB, M, l = to_byte(IDB), to_byte(M), 0
        while l == 0:
            r = randrange(1, N)  # A1
            w = bytes(self.gs_pow(r))  # A2
            h = H(2, M + w)  # A3
            l = (r - h) % N  # A4
        HB_div_HA = H(1, IDB + self.hid_s_byte) * self.h1_inv
        S = fast_kG(l * (1 - HB_div_HA) % N, self.k_ds_list) + fast_kG(l * HB_div_HA % N, _kP1)  # A5
        K = KDF(to_byte([S, w, IDB]), len(M) << 3)  # A6
        c = bytes(Mi ^ Ki for Mi, Ki in zip(M, K))  # A7
        return c, h, S  # A8

    def Unsigncrypt(self, IDA, c_, h_, S_):
        if not 0 < h_ < N or not S_ or not S_.is_on_curve():  # B1、B2
            return False
        HA_div_HB = H(1, to_byte(IDA) + self.hid_s_byte) * self.h1_inv % N
        P = fast_kG(N + 1 - HA_div_HB, self.k_de2_list) + fast_kG(HA_div_HB, self.k_Ps_list)  # B3
        t = self.gs_pow(h_)  # B4
        w_ = bytes(e(S_, P) * t)  # B5
        K_ = KDF(to_byte([S_, w_, self.ID_byte]), len(c_) << 3)  # B6
        M_ = bytes(ci ^ Ki for ci, Ki in zip(c_, K_))  # B7
        h2 = H(2, M_ + w_)
        return h2 == h_  # B8

    # 文献[1]
    def Signcrypt1(self, M, IDR):
        IDR, M, l = to_byte(IDR), to_byte(M), 0
        Q = fast_kG(H(1, IDR + self.hid_s_byte), _kP1) + self.Ppub_e  # A.1
        while l == 0:
            r = randrange(1, N)  # A.2
            w = bytes(self.gs_pow(r))  # A.3
            h = H(2, M + w)  # A.4
            l = (r - h) % N  # A.5
        S = fast_kG(l, self.k_ds_list)  # A.6
        T = Q * r  # A.7
        K = KDF(to_byte([T, w, IDR]), len(M) << 3)  # 此处KDF对应文中H3
        c = bytes(Mi ^ Ki for Mi, Ki in zip(M, K))  # A.8
        return c, S, T  # A.9

    def Unsigncrypt1(self, IDS, c, S, T):
        w_ = self.e_de(T)  # B.1 e(T, sk_IDR)
        w_byte = bytes(w_)
        K_ = KDF(to_byte([T, w_byte, self.ID_byte]), len(c) << 3)  # 此处KDF对应文中H3
        M_ = bytes(ci ^ Ki for ci, Ki in zip(c, K_))  # B.2
        h_ = H(2, M_ + w_byte)  # B.3
        t = self.gs_pow(h_)  # B.4
        P = fast_kG(H(1, to_byte(IDS) + self.hid_s_byte), _kP2) + self.Ppub_s  # B.5
        return e(S, P) * t == w_  # B.6


def test_signenc(test_num):
    IDA, IDB = 'ALICE123@YAHOO.COM', 'BILL456@YAHOO.COM'
    kgc = SM9(ks=-1, ke=-1)
    sm9_A, sm9_B = [kgc.KGC_gen_user(ID) for ID in (IDA, IDB)]
    sm9_sigenc_A, sm9_sigenc_B = [SM9_SIGNENC(sm9, kgc.ks) for sm9 in (sm9_A, sm9_B)]
    M_list = ['Signcrypt test' + str(i) for i in range(test_num)]
    print('\n--------------------签密（测试%d次）--------------------' % test_num)
    enc_list1, enc_list2, enc_list3 = [], [], []
    time_1 = time.perf_counter()
    # 本文
    for i in range(test_num):
        enc_list1.append(sm9_sigenc_A.Signcrypt(M_list[i], IDB))
    time_2 = time.perf_counter()
    # 文献[1]
    for i in range(test_num):
        enc_list2.append(sm9_sigenc_A.Signcrypt1(M_list[i], IDB))
    time_3 = time.perf_counter()
    # SM9普通签名+加密
    for i in range(test_num):
        sig = sm9_A.sign(M_list[i], outbytes=False)
        C = sm9_A.encrypt(IDB, M_list[i], outbytes=False)
        enc_list3.append((sig, C))
    time_4 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    print('签名+加密\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))

    print('\n-------------------验签解密（测试%d次）------------------' % test_num)
    res1, res2, res3 = [], [], []
    time_1 = time.perf_counter()
    # 本文
    for i in range(test_num):
        res1.append(sm9_sigenc_B.Unsigncrypt(IDA, *enc_list1[i]))
    time_2 = time.perf_counter()
    # 文献[1]
    for i in range(test_num):
        res2.append(sm9_sigenc_B.Unsigncrypt1(IDA, *enc_list2[i]))
    time_3 = time.perf_counter()
    # SM9普通解密+验签
    for i in range(test_num):
        sig, C = enc_list3[i]
        res, M_ = sm9_B.decrypt(C)
        res3.append(sm9_B.verify(IDA, M_, sig))
    time_4 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    print('解密+验签\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
    assert all(res1) and all(res2) and all(res3)


# ————————————————————————————————————论文—基于国密算法SM9的环签密方案—实验代码————————————————————————————————————
# 文献[1]：包嘉斌. 基于SM9标识密码算法的环签密方案设计及其应用研究[D]. 武汉: 武汉大学, 2022
class SM9_RINGSIGNENC(SM9):
    def __init__(self, sm9, ks):  # ks是签名私钥
        self.ID, self.ID_byte, self.Ppub_s, self.gs = sm9.ID, sm9.ID_byte, sm9.Ppub_s, sm9.gs
        self.k_ds_list, self.gs_comb_list, self.hid_s_byte = sm9.k_ds_list, sm9.gs_comb_list, sm9.hid_s_byte
        # 本文需要
        self.h1, ds = H(1, self.ID_byte + self.hid_s_byte), self.k_ds_list[0][1]
        self.g1_comb_list, self.g2_comb_list = get_comb_list(e(ds, P2)), get_comb_list(e(ds, self.Ppub_s))
        # 方案一需要
        self.k_ds2_list = get_kP_list(fast_kG(ks, self.k_ds_list))
        self.k_de0_list = get_kP_list(fast_kG(mod_inv(self.h1 + ks, N), _kP2))
        de = fast_kG(ks, self.k_de0_list)
        self.k_de_list = get_kP_list(de)
        # 方案二需要（本文描述的是方案二，文中未体现方案一）
        self.h1_inv = mod_inv(self.h1, N)
        self.k_de2_list, self.k_Ps_list = get_kP_list(fast_kG(ks, self.k_de_list)), get_kP_list(self.Ppub_s)
        # 文献[1]需要
        self.de_a_list, self.k_Pe_list = get_a_list(de), get_kP_list(fast_kG(ks, _kP1))
        self.e_P1P2_comb_list = get_comb_list(e(P1, P2))

    # 本文
    def Signcrypt(self, M, ID_list, IDR, pi=None, r_list=None, algo=1):
        M, IDR, n = to_byte(M), to_byte(IDR), len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        r_list = r_list if r_list else [randrange(1, N) for _ in range(n + 2)]  # r0=r_list[pi],r=r_list[n],ρ=r_list[-1]
        r0, rho, r = r_list[pi], r_list.pop(), r_list.pop()
        ID_list = [to_byte(ID) for ID in ID_list]
        sum_rivi, sum_ri = 0, 0  # 不含序号π
        for i in [i for i in range(n) if i != pi]:
            sum_rivi, sum_ri = sum_rivi + r_list[i] * H(1, ID_list[i] + self.hid_s_byte), sum_ri + r_list[i]
        beta = comb_pow(N - sum_rivi * r % N, self.g1_comb_list) * comb_pow(N - sum_ri * r % N, self.g2_comb_list) \
                * self.gs_pow(N - rho * r % N)
        r_r0 = r * r0 % N
        w = bytes(self.gs_pow(r_r0))
        h = H(2, to_byte([ID_list, M, w, beta]))
        r_list[pi] = ((r_r0 - h) * mod_inv(r, N) + rho) % N
        if algo == 1:
            S = fast_kG(r * H(1, IDR + self.hid_s_byte) % N, self.k_ds_list) + fast_kG(r, self.k_ds2_list)
        else:
            vR_div_vS = H(1, IDR + self.hid_s_byte) * self.h1_inv
            S = fast_kG(r * (1 - vR_div_vS) % N, self.k_ds_list) + fast_kG(r * vR_div_vS % N, _kP1)
        K = KDF(to_byte([r_list, w, IDR]), len(M) << 3)
        C = bytes(Mi ^ Ki for Mi, Ki in zip(M, K))
        return C, h, S, beta, r_list

    def Unsigncrypt(self, ID_list, C_, h_, S_, beta_, r_list, algo=1):
        if not 0 < h_ < N or not S_.is_on_curve():
            return False
        for ri_ in r_list:
            if not 0 < ri_ < N:
                return False
        ID_list = [to_byte(ID) for ID in ID_list]
        sum_rivi, sum_ri = 0, 0
        for ri_, IDi in zip(r_list, ID_list):
            sum_rivi, sum_ri = sum_rivi + ri_ * H(1, IDi + self.hid_s_byte), sum_ri + ri_
        if algo == 1:
            P = fast_kG(sum_rivi % N, self.k_de0_list) + fast_kG(sum_ri % N, self.k_de_list)
        else:
            sum_rivi_div_vR = sum_rivi * self.h1_inv % N
            P = fast_kG((sum_ri - sum_rivi_div_vR) % N, self.k_de2_list) + fast_kG(sum_rivi_div_vR, self.k_Ps_list)
        t = self.gs_pow(h_)
        w_ = bytes(e(S_, P) * beta_ * t)
        K_ = KDF(to_byte([r_list, w_, self.ID_byte]), len(C_) << 3)
        M_ = bytes(ci ^ Ki for ci, Ki in zip(C_, K_))
        h2 = H(2, to_byte([ID_list, M_, w_, beta_]))
        return h_ == h2

    # 文献[1]环签密方案一
    def Signcrypt1(self, m, ID_list, IDR, pi=None, r_list=None, opt=True):
        m, IDR, n = to_byte(m), to_byte(IDR), len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        r_list = r_list if r_list else [randrange(1, N) for _ in range(n + 2)]  # ρ=r_list[pi],r=r_list[n],r0=r_list[-1]
        r0, r, rho = r_list.pop(), r_list.pop(), r_list[pi]
        w0 = self.gs_pow(r0)
        R_list = [fast_kG(r0 * H(1, IDR + self.hid_s_byte) % N, _kP1) + fast_kG(r0, self.k_Pe_list)]  # R0
        ID_list = [self.ID_byte if i == pi else to_byte(ID_list[i]) for i in range(n)]  # Un
        if opt:  # 优化
            sum_rivi, sum_ri = rho * self.h1, rho  # +ρ，其余-
            for i in [i for i in range(n) if i != pi]:
                sum_rivi, sum_ri = sum_rivi - r_list[i] * H(1, ID_list[i] + self.hid_s_byte), sum_ri - r_list[i]
                R_list.append(fast_kG(r_list[i], _kP1))
            H_val = comb_pow(sum_rivi % N, self.e_P1P2_comb_list) * self.gs_pow(sum_ri % N)
        else:
            H_val = e(fast_kG(rho, _kP1), fast_kG(self.h1, _kP2) + self.Ppub_s)  # 初始化H为e(ρ·P1,Pupubπ)
            for i in range(n):
                if i != pi:
                    Ri, Pupubi = fast_kG(r_list[i], _kP1), fast_kG(H(1, ID_list[i] + self.hid_s_byte), _kP2) + self.Ppub_s
                    H_val *= e(-Ri, Pupubi)
                    R_list.append(Ri)
        w = self.gs_pow(r)
        h = H(2, to_byte([m, H_val, w, ID_list]))
        R_list.insert(pi + 1, fast_kG((r - h) % N, self.k_ds_list) + fast_kG(N - rho, _kP1))  # Rπ
        C = bytes(mi ^ Ki for mi, Ki in zip(m, KDF(to_byte([R_list, w0, IDR]), len(m) << 3)))  # KDF对应H3
        return R_list, H_val, h, C

    def Unsigncrypt1(self, ID_list, R_list, H_, h_, C_, opt=True):
        w0_ = self.e_de(R_list[0])  # e(R0_, Dη)
        m_ = bytes(ci ^ Ki for ci, Ki in zip(C_, KDF(to_byte([R_list, w0_, self.ID_byte]), len(C_) << 3)))  # KDF对应H3
        ID_list = [to_byte(IDi) for IDi in ID_list]  # Un
        if opt:  # 优化
            sum_Rivi, sum_Ri = R_list[1] * H(1, ID_list[0] + self.hid_s_byte), R_list[1]
            for IDi, Ri_ in zip(ID_list[1:], R_list[2:]):
                sum_Rivi, sum_Ri = sum_Rivi + Ri_ * H(1, IDi + self.hid_s_byte), sum_Ri + Ri_
            w_ = e(sum_Rivi, P2) * e(sum_Ri, self.Ppub_s) * H_ * self.gs_pow(h_)
        else:
            w_ = H_ * self.gs_pow(h_)  # 初始化ω'为H'·t
            for IDi, Ri_ in zip(ID_list, R_list[1:]):
                Pupubi = fast_kG(H(1, IDi + self.hid_s_byte), _kP2) + self.Ppub_s
                w_ *= e(Ri_, Pupubi)
        h__ = H(2, to_byte([m_, H_, w_, ID_list]))
        return h__ == h_

    # 文献[1]环签密方案二
    def Signcrypt2(self, m, ID_list, IDR, pi=None, r_list=None):
        m, IDR, n = to_byte(m), to_byte(IDR), len(ID_list)
        pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
        r_list = r_list if r_list else [randrange(1, N) for _ in range(n + 1)]  # r0=r_list[-1]
        r0, r_pi = r_list.pop(), r_list[pi]
        R_list = [fast_kG(r0 * H(1, IDR + self.hid_s_byte) % N, _kP1) + fast_kG(r0, self.k_Pe_list)]  # R0
        ID_list = [self.ID_byte if i == pi else to_byte(ID_list[i]) for i in range(n)]  # Un
        sum_rivi, sum_ri = 0, 0  # sum_ri=tπ
        for i in [i for i in range(n) if i != pi]:
            sum_rivi, sum_ri = sum_rivi + r_list[i] * H(1, ID_list[i] + self.hid_s_byte), sum_ri + r_list[i]
            R_list.append(fast_kG(r_list[i], self.k_Pe_list))
        w0 = self.gs_pow(r0)
        R = fast_kG(r_pi, _kP1) + fast_kG(sum_ri % N, self.k_Pe_list)
        w = w0 * e(R, self.Ppub_s)
        h = H(2, to_byte([w, m, ID_list]))
        R_list.insert(pi + 1, fast_kG((r_pi - h - sum_rivi) % N, self.k_ds_list))  # Rπ
        C = bytes(mi ^ Ki for mi, Ki in zip(m, KDF(to_byte([R_list, w0, IDR]), len(m) << 3)))  # KDF对应H3
        return h, R_list, C

    def Unsigncrypt2(self, ID_list, h_, R_list, C_, opt=True):
        w0_ = self.e_de(R_list[0])  # e(R0_, Dη)
        m_ = bytes(ci ^ Ki for ci, Ki in zip(C_, KDF(to_byte([R_list, w0_, self.ID_byte]), len(C_) << 3)))  # KDF对应H3
        ID_list = [to_byte(IDi) for IDi in ID_list]  # Un
        if opt:  # 优化
            sum_Rivi, sum_Ri = R_list[1] * H(1, ID_list[0] + self.hid_s_byte), R_list[1]
            for IDi, Ri_ in zip(ID_list[1:], R_list[2:]):
                sum_Rivi, sum_Ri = sum_Rivi + Ri_ * H(1, IDi + self.hid_s_byte), sum_Ri + Ri_
            w_ = w0_ * self.gs_pow(h_) * e(sum_Rivi, P2) * e(sum_Ri, self.Ppub_s)
        else:
            w_ = w0_ * self.gs_pow(h_)  # 初始化ω'为ω0'·g^h'
            for IDi, Ri_ in zip(ID_list, R_list[1:]):
                w_ *= e(Ri_, fast_kG(H(1, IDi + self.hid_s_byte), _kP2) + self.Ppub_s)
        return h_ == H(2, to_byte([w_, m_, ID_list]))


def test_ringsignenc(n_list, test_num_list):
    IDA, IDB = 'ALICE123@YAHOO.COM', 'BILL456@YAHOO.COM'  # 签名者、接收者
    kgc = SM9(ks=-1, ke=-1)
    sm9_A, sm9_B = [kgc.KGC_gen_user(ID) for ID in (IDA, IDB)]
    sm9_Rs_A = SM9_RING(sm9_A)
    raw_ID_list = [IDA + str(i) for i in range(max(n_list) << 1)]
    sm9_Rse_A, sm9_Rse_B = [SM9_RINGSIGNENC(sm9, kgc.ks) for sm9 in (sm9_A, sm9_B)]
    M_list = ['Ring signcrypt test' + str(i) for i in range(max(test_num_list))]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------环签密（%d个环用户，测试%d次）----------------' % (n, test_num))
        ID_lists = [sample(raw_ID_list, n) for _ in range(test_num)]
        pi_list = [randrange(0, n) for _ in range(test_num)]
        r_lists = [[randrange(1, N) for _ in range(n + 2)] for __ in range(test_num)]
        for i in range(test_num):
            ID_lists[i][pi_list[i]] = IDA
        enc_list1, enc_list2, enc_list3, enc_list4, enc_list5 = [], [], [], [], []
        time_1 = time.perf_counter()
        # 文献[1]方案1
        for i in range(test_num):
            enc_list1.append(sm9_Rse_A.Signcrypt1(M_list[i], ID_lists[i], IDB, pi_list[i], r_lists[i][:]))
        time_2 = time.perf_counter()
        # 文献[1]方案2
        for i in range(test_num):
            enc_list2.append(sm9_Rse_A.Signcrypt2(M_list[i], ID_lists[i], IDB, pi_list[i], r_lists[i][:-1]))
        time_3 = time.perf_counter()
        # SM9环签名（fastest）+加密
        for i in range(test_num):
            sig = sm9_Rs_A.sign3(M_list[i], ID_lists[i], pi_list[i], r_lists[i][:])
            C = sm9_A.encrypt(IDB, M_list[i], outbytes=False)
            enc_list3.append((sig, C))
        time_4 = time.perf_counter()
        # 本文方案一
        for i in range(test_num):
            enc_list4.append(sm9_Rse_A.Signcrypt(M_list[i], ID_lists[i], IDB, pi_list[i], r_lists[i][:], algo=1))
        time_5 = time.perf_counter()
        # 本文方案二
        for i in range(test_num):
            enc_list5.append(sm9_Rse_A.Signcrypt(M_list[i], ID_lists[i], IDB, pi_list[i], r_lists[i][:], algo=2))
        time_6 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]方案1\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
        print('文献[1]方案2\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
        print('环签名+加密\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, time_relative / (time_4 - time_3)))
        print('本文方案一\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, time_relative / (time_5 - time_4)))
        print('本文方案二\t耗时%.2f ms \t相对速率%.2f' % ((time_6 - time_5) * 1000 / test_num, time_relative / (time_6 - time_5)))

        print('\n---------------------解密验证（测试%d次）--------------------' % test_num)
        res1, res2, res3, res4, res5 = [], [], [], [], []
        time_1 = time.perf_counter()
        # 文献[1]方案1
        for i in range(test_num):
            res1.append(sm9_Rse_B.Unsigncrypt1(ID_lists[i], *enc_list1[i]))
        time_2 = time.perf_counter()
        # 文献[2]
        for i in range(test_num):
            res2.append(sm9_Rse_B.Unsigncrypt2(ID_lists[i], *enc_list2[i]))
        time_3 = time.perf_counter()
        # SM9普通解密+环验签（fastest）
        for i in range(test_num):
            sig, C = enc_list3[i]
            res, M_ = sm9_B.decrypt(C)
            res3.append(sm9_Rs_A.verify3(M_, ID_lists[i], *sig))
        time_4 = time.perf_counter()
        # 本文方案一
        for i in range(test_num):
            res4.append(sm9_Rse_B.Unsigncrypt(ID_lists[i], *enc_list4[i], algo=1))
        time_5 = time.perf_counter()
        # 本文方案二
        for i in range(test_num):
            res5.append(sm9_Rse_B.Unsigncrypt(ID_lists[i], *enc_list5[i], algo=2))
        time_6 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]方案1\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
        print('文献[1]方案2\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
        print('解密+环验签\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, time_relative / (time_4 - time_3)))
        print('本文方案一\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, time_relative / (time_5 - time_4)))
        print('本文方案二\t耗时%.2f ms \t相对速率%.2f' % ((time_6 - time_5) * 1000 / test_num, time_relative / (time_6 - time_5)))
        assert all(res1) and all(res2) and all(res3) and all(res4) and all(res5)


# ————————————————————————————————————论文—基于国密算法SM9的广播加密快速实现—实验代码————————————————————————————————————
# 文献[1]：赖建昌, 黄欣沂, 何德彪. 一种基于商密SM9的高效标识广播加密方案[J]. 计算机学报, 2021, 44(5): 897-907
from itertools import combinations  # 组合
# 密码累加器，计算p(α)P1 或 fi(α)P1
def accumulator1(Ppub_list, h_list, fi_alpha=False):  # 利用组合，直接乘（最慢）
    n = len(h_list) - 1 if fi_alpha else len(h_list)
    P = Ppub_list[n] + Ppub_list[n - 1] * (sum(h_list) % N)
    for i in range(2, n + 1):
        zi = 0
        for c in combinations(h_list, i):
            h_product = c[0]
            for h in c[1:]:
                h_product = h_product * h % N
            zi += h_product
        P = P + Ppub_list[n - i] * (zi % N)
    if fi_alpha:
        h_product = h_list[0]
        for h in h_list[1:]:
            h_product = h_product * h % N
        return P, h_product
    return P


def accumulator2(Ppub_list, h_list, fi_alpha=False):  # 利用组合，字典记录每一步的积
    n = len(h_list)
    num_tuple = tuple(range(n))
    dict_last, dict_now = dict(((i,), h_list[i]) for i in num_tuple), {}  # 组合→h值的积
    if fi_alpha:
        n -= 1
    P = Ppub_list[n] + Ppub_list[n - 1] * (sum(h_list) % N)
    for i in range(2, n + 1):
        zi = 0
        for c in combinations(num_tuple, i):
            dict_now[c] = h_product = dict_last[c[:-1]] * h_list[c[-1]] % N
            zi += h_product
        P = P + Ppub_list[n - i] * (zi % N)
        dict_last, dict_now = dict_now, dict_last
        dict_now.clear()
    return (P, dict_last[num_tuple[:-1]] * h_list[num_tuple[-1]] % N) if fi_alpha else P


def accumulator3(Ppub_list, h_list, fi_alpha=False):  # 递归计算（比前2快，仍会指数爆炸）
    n = len(h_list)
    z_list = [0 for _ in range(n)]
    for i in range(n):
        cal_z_list(h_list[i], 0, h_list[i + 1:], z_list)
    if fi_alpha:
        n -= 1
    P = Ppub_list[n]
    for i in range(n):
        P = P + Ppub_list[n - 1 - i] * (z_list[i] % N)
    return (P, z_list[-1]) if fi_alpha else P


# 密码累加器系数递归计算O(2^n) 可追踪环签名、广播加密、撤销加密，n到20就很慢，这个函数是罪魁祸首
def cal_z_list(start, level, res_list, z_list):
    z_list[level] += start
    for i in range(len(res_list)):
        cal_z_list(start * res_list[i] % N, level + 1, res_list[i+1:], z_list)


def cal_z_list2(h_list):  # Π(hi+x)=z_0*x^n + z_1*x^(n-1) +...+ z_(n-1)*x + z_n，递推计算系数zi，复杂度O(n^2)
    n = len(h_list)
    z_list = [0] * n  # 首项1省略
    for k in range(n):
        vk = h_list[k]
        for m in range(k, 0, -1):  # 反向遍历避免覆盖
            z_list[m] = (z_list[m] + vk * z_list[m - 1]) % N
        z_list[0] += vk
    z_list[0] %= N
    return z_list


def accumulator(Ppub_list, h_list, fi_alpha=False):  # 递推计算（最快）
    n = len(h_list) - 1 if fi_alpha else len(h_list)
    P, z_list = Ppub_list[n], cal_z_list2(h_list)
    for i in range(n):
        P += Ppub_list[n - 1 - i] * z_list[i]
    return (P, z_list[-1]) if fi_alpha else P


class SM9_BROADCAST(SM9):
    def __init__(self, sm9, ke, m):  # ke是加密私钥，m是广播人数上限
        self.ID, self.ID_byte, self.Ppub_e, self.hid_e_byte = sm9.ID, sm9.ID_byte, sm9.Ppub_e, sm9.hid_e_byte
        self.de_a_list, self.k_Pe_list, self.ge_comb_list = sm9.de_a_list, sm9.k_Pe_list, sm9.ge_comb_list
        alpha, beta = ke, randrange(1, N)
        self.Ppub_list, alpha_i = [P1, self.Ppub_e], alpha
        for i in range(m - 1):
            alpha_i = alpha_i * alpha % N
            self.Ppub_list.append(fast_kG(alpha_i, _kP1))
        # 文献[1]需要
        u = fast_kG(alpha * alpha % N, _kP2)
        self.k_u_list = get_kP_list(u)
        # 本文需要
        self.de = fast_kG(alpha * mod_inv(H(1, self.ID_byte + self.hid_e_byte) + alpha, N) % N, _kP2)  # 预计算需要
        U = fast_kG(alpha * alpha * beta % N, _kP2)
        self.k_U_list = get_kP_list(U)
        self.ge2_comb_list = get_comb_list(self.ge_pow(beta))
        self.de2_a_list = get_a_list(self.de * beta)

    # 本文
    def broad_enc(self, ID_list, klen=KEY_LEN):
        S = [to_byte(ID) for ID in ID_list]
        r = randrange(1, N)
        C1 = fast_kG(N - r, self.k_U_list)
        w = comb_pow(r, self.ge2_comb_list)
        h_list = [H(1, ID + self.hid_e_byte) for ID in S]
        C2 = accumulator(self.Ppub_list, h_list) * r
        K = KDF(to_byte([C1, C2, w, S]), klen)
        return K, C1, C2

    def broad_dec(self, ID_list, C1, C2, klen=KEY_LEN):
        S = [to_byte(ID) for ID in ID_list]
        h_list = [H(1, ID + self.hid_e_byte) for ID in S if ID != self.ID_byte]
        fi_alpha_P1, h_product = accumulator(self.Ppub_list, h_list, True)
        h_product_inv = mod_inv(h_product, N)
        w_ = e(fi_alpha_P1 * h_product_inv, C1) * e_fast(C2 * h_product_inv, self.de2_a_list)
        K_ = KDF(to_byte([C1, C2, w_, S]), klen)
        return K_

    # 文献[1]
    def broad_enc1(self, ID_list, klen=KEY_LEN):
        S = [to_byte(ID) for ID in ID_list]
        r = randrange(1, N)
        C1 = fast_kG(N - r, self.k_u_list)
        w = bytes(self.ge_pow(r))
        h_list = [H(1, ID + self.hid_e_byte) for ID in S]
        C2 = accumulator(self.Ppub_list, h_list) * r
        K = KDF(to_byte([C1, C2, w, S]), klen)
        return K, C1, C2

    def broad_dec1(self, ID_list, C1, C2, klen=KEY_LEN):
        S = [to_byte(ID) for ID in ID_list]
        h_list = [H(1, ID + self.hid_e_byte) for ID in S if ID != self.ID_byte]
        fi_alpha_P1, h_product = accumulator(self.Ppub_list, h_list, True)
        w_ = (e(fi_alpha_P1, C1) * self.e_de(C2)) ** mod_inv(h_product, N)
        K_ = KDF(to_byte([C1, C2, w_, S]), klen)
        return K_

    # 准备预计算数据
    def pre_cal(self, ID_list):
        S = [to_byte(ID) for ID in ID_list]
        self.S_byte = to_byte(S)
        # 加密者需要
        h_list = [H(1, ID + self.hid_e_byte) for ID in S]
        self.k_p_alpha_list = get_kP_list(accumulator(self.Ppub_list, h_list))  # V
        # 解密者需要
        del h_list[ID_list.index(self.ID)]
        fi_alpha_P1, h_product = accumulator(self.Ppub_list, h_list, True)
        h_product_inv = mod_inv(h_product, N)
        self.fi_alpha_P1 = fi_alpha_P1 * h_product_inv  # Wπ
        self.de3_a_list = get_a_list(self.de * h_product_inv)  # skπ'

    def broad_enc_pre(self, klen=KEY_LEN):
        r = randrange(1, N)
        w = self.ge_pow(r)
        C1, C2 = fast_kG(N - r, self.k_u_list), fast_kG(r, self.k_p_alpha_list)
        K = KDF(to_byte([C1, C2, w, self.S_byte]), klen)
        return K, C1, C2

    def broad_dec_pre(self, C1, C2, klen=KEY_LEN):
        w_ = e(self.fi_alpha_P1, C1) * e_fast(C2, self.de3_a_list)
        K_ = KDF(to_byte([C1, C2, w_, self.S_byte]), klen)
        return K_


# 输入广播用户数量列表、测试次数列表
def test_broadcast(n_list, test_num_list):
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9(ke=-1)
    max_n = max(n_list)
    sm9_A = SM9_BROADCAST(kgc.KGC_gen_user(IDA), kgc.ke, max_n)
    raw_ID_list = [IDA] + [IDA + str(i) for i in range(max_n - 1)]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------广播加密（%d个广播用户，测试%d次）----------------' % (n, test_num))
        res_list1, res_list2, res_list3 = [], [], []
        ID_list = raw_ID_list[:n]
        sm9_A.pre_cal(ID_list)
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res_list1.append(sm9_A.broad_enc1(ID_list))
        time_2 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res_list2.append(sm9_A.broad_enc(ID_list))
        time_3 = time.perf_counter()
        # 预计算
        for i in range(test_num):
            res_list3.append(sm9_A.broad_enc_pre())
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('预计算\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))

        print('\n---------------广播消息解密（%d个广播用户，测试%d次）--------------' % (n, test_num))
        res1, res2, res3 = [], [], []
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res1.append(sm9_A.broad_dec1(ID_list, *res_list1[i][1:]) == res_list1[i][0])
        time_2 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res2.append(sm9_A.broad_dec(ID_list, *res_list2[i][1:]) == res_list2[i][0])
        time_3 = time.perf_counter()
        # 预计算
        for i in range(test_num):
            res3.append(sm9_A.broad_dec_pre(*res_list3[i][1:]) == res_list3[i][0])
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('预计算\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
        assert all(res1) and all(res2) and all(res3)


# ————————————————————————————————————论文—基于国密算法SM9的可追踪环签名方案—实验代码————————————————————————————————————
# 文献[1]：安浩杨, 何德彪, 包子健, 等. 基于SM9数字签名的环签名及其在区块链隐私保护中的应用[J]. 计算机研究与发展, 2023, 60(11): 2545-2554
# 文献[2]：丁勇, 罗世东, 杨昌松, 等. 基于SM9标识密码算法的可否认环签名方案[J]. 信息网络安全, 2024, 24(6): 893-902
class SM9_ACCURING(SM9):
    def __init__(self, sm9, q, fast_cal=True):  # q是累加器上限
        self.ID, self.ID_byte, self.Ppub_s, self.gs = sm9.ID, sm9.ID_byte, sm9.Ppub_s, sm9.gs
        self.k_ds_list, self.gs_comb_list, self.hid_s_byte = sm9.k_ds_list, sm9.gs_comb_list, sm9.hid_s_byte
        self.ds = self.k_ds_list[0][1]
        self.h1 = H(1, self.ID_byte + self.hid_s_byte)
        self.fast_cal = fast_cal
        # 系统初始化过程中，累加器相关参数可由第三方生成
        self.s, self.u = randrange(1, N), randrange(1, N)
        self.Spub, self.L, si = fast_kG(self.s, _kP2), [P1], self.s
        for i in range(q):
            self.L.append(fast_kG(si, _kP1))
            si = si * self.s % N
        # 文献[1]参数
        self.G1, self.G2, self.G3 = [fast_kG(randrange(1, N), _kP1) for _ in range(3)]
        self.e_G2P2, self.e_G3P2 = e(self.G2, P2), e(self.G3, P2)
        self.e_G2Spub, self.e_G3Ppub = e(self.G2, self.Spub), e(self.G3, self.Ppub_s)
        if fast_cal:  # 快速计算需要的预计算数据
            self.k_G1_list, self.k_G2_list, self.k_G3_list = [get_kP_list(P) for P in (self.G1, self.G2, self.G3)]
            self.e_G2P2_comb_list, self.e_G3P2_comb_list = get_comb_list(self.e_G2P2), get_comb_list(self.e_G3P2)
            self.e_G2Spub_comb_list, self.e_G3Ppub_comb_list = get_comb_list(self.e_G2Spub), get_comb_list(self.e_G3Ppub)

    # 准备预计算数据
    def pre_cal(self, ID_list):
        Un = [to_byte(ID) for ID in ID_list]
        self.Un_byte = to_byte(Un)
        x_list = [H(1, ID_byte + self.hid_s_byte) for ID_byte in Un if ID_byte != self.ID_byte]  # 除自己以外的h1值
        mul_xi_add_s = self.u
        for xi in x_list:  # 已去掉自己的ID
            mul_xi_add_s = mul_xi_add_s * (xi + self.s) % N
        self.sum_vi = sum(x_list, self.h1) % N  # 文献[2]参数
        self.e_P1P2_comb_list = get_comb_list(e(P1, P2))  # 文献[2]参数
        self.e_dsP2_comb_list = get_comb_list(e(self.ds, P2))  # 文献[2]参数
        self.WA = fast_kG(mul_xi_add_s, _kP1)
        self.V = fast_kG(mul_xi_add_s * (self.h1 + self.s) % N, _kP1)
        self.e_VP2 = e(self.V, P2)  # 文献[1]、本文参数
        self.e_VP2_gs = self.e_VP2 * self.gs  # 本文参数
        self.e_WAdsP2 = e(self.WA + self.ds, P2)  # 本文参数
        if self.fast_cal:  # 快速计算需要更多的预计算数据
            # 文献[1]参数
            self.e_VP2_comb_list = get_comb_list(self.e_VP2)
            # 本文参数
            self.e_VP2g_comb_list = get_comb_list(self.e_VP2_gs)
            self.e_WAdsP2_comb_list = get_comb_list(self.e_WAdsP2)
            self.k_WA_list = get_kP_list(self.WA)

    def sign0(self, M, ID_list=None, pi=None, r_list=None):  # 本文签名
        if ID_list:  # 不预设ID_list
            n = len(ID_list)
            pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
            r1, r2 = r_list if r_list else (randrange(1, N), randrange(1, N))
            ID_list = [self.ID_byte if i == pi else to_byte(ID_list[i]) for i in range(n)]  # Un
            v_list = [self.h1 if i == pi else H(1, ID_list[i] + self.hid_s_byte) for i in range(n)]
            V = accumulator(self.L, v_list)
            v_list.pop(pi)
            W_pi = accumulator(self.L, v_list)
            w = self.gs_pow(r1) * e(V * r1 + W_pi * r2 + fast_kG(r2, self.k_ds_list), P2)
            h = H(2, to_byte([ID_list, M, w]))
            l = (r1 - h) % N
            R, S, T = W_pi * l, fast_kG(l, self.k_ds_list), fast_kG((r2 * mod_inv(l, N) + self.h1) % N, _kP2)
            return h, R, S, T

        r1, r2 = randrange(1, N), randrange(1, N)
        if self.fast_cal:  # 快速计算
            w = comb_pow(r1, self.e_VP2g_comb_list) * comb_pow(r2, self.e_WAdsP2_comb_list)
            h = H(2, to_byte([w, self.Un_byte, M]))
            l = (r1 - h) % N
            R, S, T = fast_kG(l, self.k_WA_list), fast_kG(l, self.k_ds_list), fast_kG((r2 * mod_inv(l, N) + self.h1) % N, _kP2)
        else:
            w = self.e_VP2_gs ** r1 * self.e_WAdsP2 ** r2
            h = H(2, to_byte([w, self.Un_byte, M]))
            l = (r1 - h) % N
            R, S, T = self.WA * l, self.ds * l, P2 * ((r2 * mod_inv(l, N) + self.h1) % N)
        return h, R, S, T

    def verify0(self, M, h, R, S, T, ID_list=None):  # 本文验签
        if not 0 < h < N:
            return False
        for P in [R, S, T]:
            if not P.is_on_curve():
                return False
        if ID_list:  # 不预设ID_list
            ID_list = [to_byte(ID) for ID in ID_list]  # Un
            v_list = [H(1, ID + self.hid_s_byte) for ID in ID_list]
            V = accumulator(self.L, v_list)
            w_ = e(R, self.Spub + T) * e(S, self.Ppub_s + T) * self.gs_pow(h) * e(V * h, P2)
            h2 = H(2, to_byte([ID_list, M, w_]))
            return h2 == h

        u = e(R, self.Spub + T) * e(S, self.Ppub_s + T)
        t = comb_pow(h, self.e_VP2g_comb_list) if self.fast_cal else self.e_VP2_gs ** h
        w_ = u * t
        h2 = H(2, to_byte([w_, self.Un_byte, M]))
        return h2 == h

    # 文献[1]
    def sign1(self, M, ID_list=None, pi=None, r_list=None):
        r1, r2, r3, k1, k2, k3, k4, k5, k6, k7 = r_list if r_list else [randrange(1, N) for _ in range(10)]
        alpha_1, alpha_2, alpha_3 = [r * self.h1 % N for r in (r1, r2, r3)]
        if ID_list:  # 不预设ID_list
            n = len(ID_list)
            pi = pi if pi is not None and 0 <= pi < n else ID_list.index(self.ID)
            ID_list = [self.ID_byte if i == pi else to_byte(ID_list[i]) for i in range(n)]  # Un
            v_list = [self.h1 if i == pi else H(1, ID_list[i] + self.hid_s_byte) for i in range(n)]
            V = accumulator(self.L, v_list)
            v_list.pop(pi)
            W_pi = accumulator(self.L, v_list)
        else:
            V, W_pi = self.V, self.WA

        if self.fast_cal:  # 快速计算
            A1 = fast_kG(r1, self.k_G1_list) + fast_kG(r2, self.k_G2_list) + fast_kG(r3, self.k_G3_list)
            A2 = W_pi + fast_kG(r1, self.k_G2_list)
            A3 = self.ds + fast_kG(r2, self.k_G3_list)
            T1 = fast_kG(k1, self.k_G1_list) + fast_kG(k2, self.k_G2_list) + fast_kG(k3, self.k_G3_list)
            T2 = fast_kG(k4, self.k_G1_list) + fast_kG(k5, self.k_G2_list) + fast_kG(k6, self.k_G3_list) + -A1 * k7
            T3 = e(-A2 * k7, P2) * comb_pow(k1, self.e_G2Spub_comb_list) * comb_pow(k4, self.e_G2P2_comb_list)
            T4 = e(-A3 * k7, P2) * comb_pow(k2, self.e_G3Ppub_comb_list) * comb_pow(k5, self.e_G3P2_comb_list)
        else:
            A1 = self.G1 * r1 + self.G2 * r2 + self.G3 * r3
            A2 = W_pi + self.G2 * r1
            A3 = self.ds + self.G3 * r2
            T1 = self.G1 * k1 + self.G2 * k2 + self.G3 * k3
            T2 = self.G1 * k4 + self.G2 * k5 + self.G3 * k6 + -A1 * k7
            T3 = e(A2, P2) ** (N - k7) * self.e_G2Spub ** k1 * self.e_G2P2 ** k4
            T4 = e(A3, P2) ** (N - k7) * self.e_G3Ppub ** k2 * self.e_G3P2 ** k5
        ch = H(2, to_byte([A1, A2, A3, T1, T2, T3, T4, M]))
        s1, s2, s3, s4, s5, s6, s7 = [(k + ch * r) % N for k, r in zip(
            [k1, k2, k3, k4, k5, k6, k7], [r1, r2, r3, alpha_1, alpha_2, alpha_3, self.h1])]
        return ch, s1, s2, s3, s4, s5, s6, s7, A1, A2, A3, T1, T2, T3, T4, V

    def verify1(self, M, sig, ID_list=None):
        ch, s1, s2, s3, s4, s5, s6, s7, A1, A2, A3, T1, T2, T3, T4, V = sig
        for t in [ch, s1, s2, s3, s4, s5, s6, s7]:
            if not 0 < t < N:
                return False
        for P in [A1, A2, A3, T1, T2, V]:
            if not P.is_on_curve():
                return False
        if ID_list:  # 不预设ID_list
            ID_list = [to_byte(ID) for ID in ID_list]  # Un
            v_list = [H(1, ID + self.hid_s_byte) for ID in ID_list]
            V_ = accumulator(self.L, v_list)
            if V != V_:
                return False
            e_VP2_ch = e(V * ch, P2)
        else:
            e_VP2_ch = comb_pow(ch, self.e_VP2_comb_list) if self.fast_cal else e(V, P2) ** ch
        return all([ch == H(2, to_byte([A1, A2, A3, T1, T2, T3, T4, M])),
                    T1 == fast_kG(s1, self.k_G1_list) + fast_kG(s2, self.k_G2_list) + fast_kG(s3, self.k_G3_list) + -A1 * ch,
                    T2 == fast_kG(s4, self.k_G1_list) + fast_kG(s5, self.k_G2_list) + fast_kG(s6, self.k_G3_list) + -A1 * s7,
                    T3 == e(-A2 * s7, P2) * comb_pow(s1, self.e_G2Spub_comb_list) * comb_pow(s4, self.e_G2P2_comb_list)
                    * e(-A2 * ch, self.Spub) * e_VP2_ch,
                    T4 == e(-A3 * s7, P2) * comb_pow(s2, self.e_G3Ppub_comb_list) * comb_pow(s5, self.e_G3P2_comb_list)
                    * e(-A3 * ch, self.Ppub_s) * self.gs_pow(ch)]) if self.fast_cal else \
            all([ch == H(2, to_byte([A1, A2, A3, T1, T2, T3, T4, M])),
                 T1 == self.G1 * s1 + self.G2 * s2 + self.G3 * s3 + -A1 * ch,
                 T2 == self.G1 * s4 + self.G2 * s5 + self.G3 * s6 + -A1 * s7,
                 T3 == e(A2, P2) ** (N - s7) * self.e_G2Spub ** s1 * self.e_G2P2 ** s4 * e(A2, self.Spub) ** (N - ch) * e_VP2_ch,
                 T4 == e(A3, P2) ** (N - s7) * self.e_G3Ppub ** s2 * self.e_G3P2 ** s5 * e(A3, self.Ppub_s) ** (N - ch) * self.gs ** ch])

    # 文献[2]
    def sign2(self, M, ID_list, pi=None, r_list=None):
        pi = pi if pi else ID_list.index(self.ID)
        r_list = r_list if r_list else [randrange(1, N) for _ in range(len(ID_list))]
        r = r_list.pop(pi)
        alpha = self.gs_pow(r)
        R_list = [fast_kG(ri, _kP1) for ri in r_list]  # 不含Rπ
        sum_ri_out_pi = sum(r_list) % N
        beta = self.gs_pow(sum_ri_out_pi) * comb_pow(sum_ri_out_pi * self.sum_vi % N, self.e_P1P2_comb_list)
        gamma = comb_pow(r * self.sum_vi % N, self.e_dsP2_comb_list)
        w = alpha * beta * gamma  # ω=α⋅β⋅γ
        h1 = H(2, to_byte([self.Un_byte, M, w]))
        l = (r - h1) % N
        R_list.insert(pi, fast_kG(l, self.k_ds_list))  # Rπ = [l]skπ
        sum_vi_out_pi = self.sum_vi - self.h1  # self.h1就是vπ
        phi = comb_pow((r * self.h1 + h1 * sum_vi_out_pi) % N, self.e_dsP2_comb_list)  # φ
        return h1, R_list, phi

    def verify2(self, M, ID_list, h1, R_list, phi):
        w_ = e(sum(R_list[1:], R_list[0]), fast_kG(self.sum_vi, _kP2) + self.Ppub_s) * self.gs_pow(h1) * phi
        h_star = H(2, to_byte([self.Un_byte, M, w_]))
        return h_star == h1


# 输入环用户数量列表、测试次数列表
def test_accuring(n_list, test_num_list):
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9(ks=-1)
    max_n = max(n_list)
    sm9_A = SM9_ACCURING(kgc.KGC_gen_user(IDA), max_n, True)
    raw_ID_list = [IDA] + [IDA + str(i) for i in range(max_n - 1)]
    M_list = ['Accumulator ring signature test' + str(i) for i in range(max(test_num_list))]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------可追踪环签名（%d个环用户，测试%d次）----------------' % (n, test_num))
        ring_sig1, ring_sig2, ring_sig3 = [], [], []
        ID_list = raw_ID_list[:n]
        sm9_A.pre_cal(ID_list)
        time_1 = time.perf_counter()
        # 本文
        for i in range(test_num):
            ring_sig1.append(sm9_A.sign0(M_list[i]))
        time_2 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            ring_sig2.append(sm9_A.sign1(M_list[i]))
        time_3 = time.perf_counter()
        # 文献[2]
        for i in range(test_num):
            ring_sig3.append(sm9_A.sign2(M_list[i], ID_list, 0))
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('文献[2]\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))

        print('\n---------------环签名验证（%d个环用户，测试%d次）--------------' % (n, test_num))
        res1, res2, res3 = [], [], []
        time_1 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res1.append(sm9_A.verify0(M_list[i], *ring_sig1[i]))
        time_2 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res2.append(sm9_A.verify1(M_list[i], ring_sig2[i]))
        time_3 = time.perf_counter()
        # 文献[2]
        for i in range(test_num):
            res3.append(sm9_A.verify2(M_list[i], ID_list, *ring_sig3[i]))
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
        print('文献[1]\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
        print('文献[2]\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
        assert all(res1) and all(res2) and all(res3)


# ————————————————————————————————————论文—基于国密算法SM9的分层标识加密方案—实验代码————————————————————————————————————
class SM9_HIBE:
    def __init__(self, ID, ke=None, max_hier=None, de_list=None, kgc=None, hid_e=3, fast_cal=False):
        self.ID, self.ID_byte, self.hid_e_byte = ID, to_byte(ID), to_byte(hid_e, 1)
        if ke:  # 作为顶级KGC，给定加密主私钥（若要随机生成，可指定ke=-1）
            self.ke = ke if 0 < ke < N else randrange(1, N)
            self.Ppub_e = fast_kG(self.ke, _kP1)
            self.h1 = H(1, self.ID_byte + self.hid_e_byte)
            t1 = (self.h1 + self.ke) % N
            assert t1 != 0  # 若不满足，需重新产生加密主密钥，并更新所有用户的加密密钥
            t2 = self.ke * mod_inv(t1, N) % N
            self.de = fast_kG(t2, _kP2)  # 顶级KGC的加密私钥
            # 加密主公钥
            self.ge = e(self.Ppub_e, P2)
            self.Q_list = [fast_kG(randrange(1, N), _kP2) for _ in range(max_hier)]  # 文献[X]参数
            self.Q1, self.Q2 = self.Q_list[:2]  # 本文参数
            self.fast_cal, self.n = fast_cal, max_hier
            if fast_cal:  # 快速计算需要的预计算数据
                self.ge_comb_list = get_comb_list(self.ge)
                self.k_AP1Pe_list = get_kP_list(fast_kG(self.h1, _kP1) + self.Ppub_e)  # x_A*P1 + Ppub_e
                self.k_Qi_lists = [get_kP_list(Qi) for Qi in self.Q_list]
                self.k_Q1_list, self.k_Q2_list = self.k_Qi_lists[:2]
        if de_list:  # 作为用户，给定用户加密私钥
            self.de_list, self.kgc = de_list, kgc

    def gen_user(self, ID_list):  # 生成第k层用户
        if hasattr(self, 'ke'):  # 由顶级KGC（第1层）生成
            r, kgc = randrange(1, N), self
            H_IDk = H(1, to_byte(ID_list[-1]) + kgc.hid_e_byte)
            if kgc.fast_cal:  # 快速计算
                d1 = kgc.de + fast_kG(r, kgc.k_Q1_list) \
                     + fast_kG(r * H_IDk % N, kgc.k_Q2_list)  # de + r*Q1 + r*H_ID*Q2
                d2, d3 = fast_kG(r, kgc.k_AP1Pe_list), fast_kG(r, kgc.k_Q2_list)
            else:
                d1 = kgc.de + (kgc.Q1 + kgc.Q2 * H_IDk) * r
                d2, d3 = P1 * (r * (kgc.h1 + kgc.ke) % N), kgc.Q2 * r
        else:  # 由第k-1层用户生成
            t, kgc = randrange(1, N), self.kgc
            H_IDk_1, H_IDk = [H(1, to_byte(ID) + kgc.hid_e_byte) for ID in ID_list[-2:]]
            d1_, d2_, d3_ = self.de_list
            if kgc.fast_cal:  # 快速计算
                d1 = d1_ + d3_ * ((H_IDk - H_IDk_1) % N) + fast_kG(t, kgc.k_Q1_list) \
                     + fast_kG(t * H_IDk % N, kgc.k_Q2_list)  # d1' + (H_IDk - H_IDk-1)d3' + t*Q1 + t*H_IDk*Q2
                d2, d3 = d2_ + fast_kG(t, kgc.k_AP1Pe_list), d3_ + fast_kG(t, kgc.k_Q2_list)
            else:
                d1 = d1_ + d3_ * ((H_IDk - H_IDk_1) % N) + (kgc.Q1 + kgc.Q2 * H_IDk) * t
                H_ID1 = H(1, to_byte(ID_list[0]) + kgc.hid_e_byte)
                d2 = d2_ + (kgc.Ppub_e + P1 * H_ID1) * t  # d2' + t(Ppub + H_ID1*P1)
                d3 = d3_ + kgc.Q2 * t  # d3' + t*Q2
        de_list = [d1, d2, d3]
        return SM9_HIBE(ID=ID_list, de_list=de_list, kgc=kgc, fast_cal=kgc.fast_cal)

    def encrypt(self, ID_list, klen=KEY_LEN):  # 密钥封装，接收者为第k层用户
        ID_list = [to_byte(ID) for ID in ID_list]
        s, H_IDk = randrange(1, N), H(1, ID_list[-1] + self.hid_e_byte)
        if self.kgc.fast_cal:  # 快速计算
            C1 = fast_kG(s, self.kgc.k_AP1Pe_list)
            C2 = fast_kG(s, self.kgc.k_Q1_list) + fast_kG(s * H_IDk % N, self.kgc.k_Q2_list)  # s*Q1 + s*H_IDk*Q2
            w = comb_pow(s, self.kgc.ge_comb_list)
        else:
            C1 = (self.kgc.Ppub_e + P1 * H(1, ID_list[0] + self.hid_e_byte)) * s
            C2 = (self.kgc.Q1 + self.kgc.Q2 * H_IDk) * s  # s(Q1 + H_IDk*Q2)
            w = self.kgc.ge ** s
        K = KDF(to_byte([C1, C2, w, ID_list]), klen)
        assert K != 0
        return K, (C1, C2)

    # [基于商用密码SM9的高效分层标识加密]
    def gen_user1(self, ID_list):  # 生成第k层用户
        raw_ID_list, ID_list, k = ID_list, [to_byte(ID) for ID in ID_list], len(ID_list)
        if hasattr(self, 'ke'):  # 由顶级KGC（第1层）生成
            r, kgc = randrange(1, N), self
            if kgc.fast_cal:  # 快速计算
                d1 = kgc.de + fast_kG(r, kgc.k_Qi_lists[0])  # de + r*Q1
                for i in range(1, k):
                    H_IDi = H(1, ID_list[i] + kgc.hid_e_byte)
                    d1 = d1 + fast_kG(r * H_IDi % N, kgc.k_Qi_lists[i])
                d2 = fast_kG(r, kgc.k_AP1Pe_list)
                de_list = [d1, d2] + [fast_kG(r, kQ_list) for kQ_list in kgc.k_Qi_lists[k: kgc.n]]
            else:
                d1 = sum([kgc.Q_list[i] * H(1, ID_list[i] + kgc.hid_e_byte) for i in range(1, k)], kgc.Q_list[0])
                d1 = kgc.de + d1 * r
                d2 = P1 * (r * (kgc.h1 + kgc.ke) % N)
                de_list = [d1, d2] + [Qi * r for Qi in kgc.Q_list[k: kgc.n]]  # d1, d2, uk+1...un
        else:  # 由第k-1层用户生成
            t, kgc = randrange(1, N), self.kgc
            (d1_, d2_, uk_), uk1_list = self.de_list[:3], self.de_list[3:]
            if kgc.fast_cal:  # 快速计算
                d1 = d1_ + fast_kG(t, kgc.k_Qi_lists[0])  # d1' + t*Q1
                for i in range(1, k):
                    H_IDi = H(1, ID_list[i] + kgc.hid_e_byte)
                    d1 = d1 + fast_kG(t * H_IDi % N, kgc.k_Qi_lists[i])  # + t*H_ID2*Q2 +...+ t*H_IDk*Qk
                d1 = d1 + uk_ * H_IDi  # + H_IDk*uk'
                d2 = d2_ + fast_kG(t, kgc.k_AP1Pe_list)  # d2' + t(Ppub + H_ID1*P)
                de_list = [d1, d2] + [uk1_list[i - k] + fast_kG(t, kgc.k_Qi_lists[i]) for i in range(k, kgc.n)]
            else:
                d1 = kgc.Q_list[0]  # Q1
                for i in range(1, k):
                    H_IDi = H(1, ID_list[i] + kgc.hid_e_byte)
                    d1 = d1 + kgc.Q_list[i] * H_IDi  # + H_ID2*Q2 +...+ H_IDk*Qk
                d1 = d1_ + uk_ * H_IDi + d1 * t  # d1' + H_IDk*uk' + t*...
                d2 = d2_ + (kgc.Ppub_e + P1 * H(1, ID_list[0] + kgc.hid_e_byte)) * t
                de_list = [d1, d2] + [uk1_list[i - k] + kgc.Q_list[i] * t for i in range(k, kgc.n)]
        return SM9_HIBE(ID=raw_ID_list, de_list=de_list, kgc=kgc, fast_cal=kgc.fast_cal)

    def encrypt1(self, ID_list, klen=KEY_LEN):  # 密钥封装，接收者为第k层用户
        s, ID_list, k = randrange(1, N), [to_byte(ID) for ID in ID_list], len(ID_list)
        if self.kgc.fast_cal:  # 快速计算
            C1 = fast_kG(s, self.kgc.k_AP1Pe_list)
            C2 = sum([fast_kG(s * H(1, ID_list[i] + self.hid_e_byte) % N, self.kgc.k_Qi_lists[i]) for i in range(1, k)],
                     fast_kG(s, self.kgc.k_Qi_lists[0]))  # s*Q1 + s*H_ID2*Q2 +...+ s*H_IDk*Qk
            w = comb_pow(s, self.kgc.ge_comb_list)
        else:
            C1 = (self.kgc.Ppub_e + P1 * H(1, ID_list[0] + self.hid_e_byte)) * s
            C2 = sum([self.kgc.Q_list[i] * H(1, ID_list[i] + self.hid_e_byte) for i in range(1, k)],
                     self.kgc.Q_list[0]) * s  # s(Q1 + H_ID2*Q2 +...+ H_IDk*Qk)
            w = self.kgc.ge ** s
        K = KDF(to_byte([C1, C2, w, ID_list]), klen)
        assert K != 0
        return K, (C1, C2)

    def decrypt(self, CT, klen=KEY_LEN):  # 第k层用户解封装
        (C1, C2), (d1, d2) = CT, self.de_list[:2]
        w_ = e(C1, d1) * e(d2, C2).frobenius6()  # A=e(C1, d1), B=e(d2, C2), w'=A/B
        K_ = KDF(to_byte([C1, C2, w_, self.ID_byte]), klen)
        return K_ if K_ else False


# 输入最大层数、测试次数
def test_HIBE(n, test_num):
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9_HIBE(IDA, -1, n, fast_cal=True)
    raw_ID_list = [IDA] + [IDA + str(i) for i in range(n - 1)]

    print('\n----------------KGC生成用户（依次生成第2~%d层，测试%d次）----------------' % (n, test_num))
    kgc_gen_users1, kgc_gen_users2 = [], []
    time_1 = time.perf_counter()
    # 本文
    for k in range(2, n + 1):
        for _ in range(test_num):
            user1 = kgc.gen_user(raw_ID_list[:k])
        kgc_gen_users1.append(user1)
    time_2 = time.perf_counter()
    # 对照组
    for k in range(2, n + 1):
        for _ in range(test_num):
            user2 = kgc.gen_user1(raw_ID_list[:k])
        kgc_gen_users2.append(user2)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------用户生成用户（依次生成第3~%d层，测试%d次）----------------' % (n, test_num))
    user_gen_users1, user_gen_users2 = [kgc_gen_users1[0]], [kgc_gen_users2[0]]  # 第2层用户作为初始节点
    time_1 = time.perf_counter()
    # 本文
    for k in range(3, n + 1):
        for _ in range(test_num):
            user_next1 = user_gen_users1[-1].gen_user(raw_ID_list[:k])
        user_gen_users1.append(user_next1)
    time_2 = time.perf_counter()
    # 对照组
    for k in range(3, n + 1):
        for _ in range(test_num):
            user_next2 = user_gen_users2[-1].gen_user1(raw_ID_list[:k])
        user_gen_users2.append(user_next2)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------加密（第2~%d层依次，测试%d次）----------------' % (n, test_num))
    K_CTs1, K_CTs2 = [], []
    encryptor1, encryptor2 = user_gen_users1[-1], user_gen_users2[-1]
    time_1 = time.perf_counter()
    # 本文
    for k in range(2, n + 1):
        for _ in range(test_num):
            K_CTs1.append(encryptor1.encrypt(raw_ID_list[:k]))
    time_2 = time.perf_counter()
    # 对照组
    for k in range(2, n + 1):
        for _ in range(test_num):
            K_CTs2.append(encryptor2.encrypt1(raw_ID_list[:k]))
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------解密（第2~%d层依次，测试%d次）----------------' % (n, test_num))
    time_1 = time.perf_counter()
    # 本文
    for user in user_gen_users1:
        for _ in range(test_num):
            K, CT = K_CTs1.pop(0)
            assert K == user.decrypt(CT)
    time_2 = time.perf_counter()
    # 对照组
    for user in user_gen_users2:
        for _ in range(test_num):
            K, CT = K_CTs2.pop(0)
            assert K == user.decrypt(CT)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))


# ————————————————————————————————————论文—基于国密算法SM9的分层标识签名方案—实验代码————————————————————————————————————
class SM9_HIBS:
    def __init__(self, ID, ks=None, max_hier=None, ds_list=None, kgc=None, h1=None, hid_s=3, fast_cal=False):
        self.ID, self.ID_byte, self.hid_s_byte = ID, to_byte(ID), to_byte(hid_s, 1)
        if ks:  # 作为顶级KGC，给定签名主私钥（若要随机生成，可指定ks=-1）
            self.ks = ks if 0 < ks < N else randrange(1, N)
            self.Ppub_s = fast_kG(self.ks, _kP2)
            self.h1 = H(1, self.ID_byte + self.hid_s_byte)
            t1 = (self.h1 + self.ks) % N
            assert t1 != 0  # 若不满足，需重新产生签名主密钥，并更新所有用户的签名密钥
            t2 = self.ks * mod_inv(t1, N) % N
            self.ds = fast_kG(t2, _kP1)  # 顶级KGC的签名私钥
            # 签名主公钥
            self.gs = e(P1, self.Ppub_s)
            self.Q_list = [fast_kG(randrange(1, N), _kP1) for _ in range(max_hier)]  # 文献[X]参数
            self.Q1, self.Q2 = self.Q_list[:2]  # 本文参数
            self.fast_cal, self.n = fast_cal, max_hier
            if fast_cal:  # 快速计算需要的预计算数据
                self.gs_comb_list = get_comb_list(self.gs)
                self.k_AP2Ps_list = get_kP_list(fast_kG(self.h1, _kP2) + self.Ppub_s)  # x_A*P2 + Ppub_s
                self.k_Qi_lists = [get_kP_list(Qi) for Qi in self.Q_list]
                self.k_Q1_list, self.k_Q2_list = self.k_Qi_lists[:2]
        if ds_list:  # 作为用户，给定用户签名私钥
            self.ds_list, self.kgc = ds_list, kgc
            self.H_ID1, self.H_IDk = kgc.h1, h1

    def gen_user(self, ID_list):  # 生成第k层用户
        if hasattr(self, 'ks'):  # 由顶级KGC（第1层）生成
            r, kgc = randrange(1, N), self
            H_IDk = H(1, to_byte(ID_list[-1]) + kgc.hid_s_byte)
            if kgc.fast_cal:  # 快速计算
                d1 = kgc.ds + fast_kG(r, kgc.k_Q1_list) \
                     + fast_kG(r * H_IDk % N, kgc.k_Q2_list)  # de + r*Q1 + r*H_ID*Q2
                d2, d3 = fast_kG(r, kgc.k_AP2Ps_list), fast_kG(r, kgc.k_Q2_list)
            else:
                d1 = kgc.ds + (kgc.Q1 + kgc.Q2 * H_IDk) * r
                d2, d3 = P2 * (r * (kgc.h1 + kgc.ks) % N), kgc.Q2 * r
        else:  # 由第k-1层用户生成
            t, kgc = randrange(1, N), self.kgc
            H_IDk_1, H_IDk = self.H_IDk, H(1, to_byte(ID_list[-1]) + kgc.hid_s_byte)
            d1_, d2_, d3_ = self.ds_list
            if kgc.fast_cal:  # 快速计算
                d1 = d1_ + d3_ * ((H_IDk - H_IDk_1) % N) + fast_kG(t, kgc.k_Q1_list) \
                     + fast_kG(t * H_IDk % N, kgc.k_Q2_list)  # d1' + (H_IDk - H_IDk-1)d3' + t*Q1 + t*H_IDk*Q2
                d2, d3 = d2_ + fast_kG(t, kgc.k_AP2Ps_list), d3_ + fast_kG(t, kgc.k_Q2_list)
            else:
                d1 = d1_ + d3_ * ((H_IDk - H_IDk_1) % N) + (kgc.Q1 + kgc.Q2 * H_IDk) * t
                d2 = d2_ + (kgc.Ppub_s + P2 * self.H_ID1) * t  # d2' + t(Ppub + H_ID1*P2)
                d3 = d3_ + kgc.Q2 * t  # d3' + t*Q2
        ds_list = [d1, d2, d3]
        return SM9_HIBS(ID=ID_list, ds_list=ds_list, kgc=kgc, h1=H_IDk, fast_cal=kgc.fast_cal)

    def pre_cal(self):
        self.k_ds1_list, self.k_ds2_list = [get_kP_list(ds) for ds in self.ds_list[:2]]

    def sign(self, M):  # 第k层用户签名
        l = 0
        while l == 0:
            s = randrange(1, N)
            w = comb_pow(s, self.kgc.gs_comb_list) if self.kgc.fast_cal else self.kgc.gs ** s
            h = H(2, to_byte([M, w]))
            l = (s - h) % N
        S1 = fast_kG(l, self.k_ds1_list) if self.kgc.fast_cal else self.ds_list[0] * l  # l*ds1
        S2 = fast_kG(l, self.k_ds2_list) if self.kgc.fast_cal else self.ds_list[1] * l  # l*ds2
        return h, S1, S2

    def verify(self, ID_list, M_, sig_):  # 验签
        h_, S1_, S2_ = sig_
        if not 0 < h_ < N or not S1_.is_on_curve() or not S2_.is_on_curve():
            return False
        H_IDk = H(1, to_byte(ID_list[-1]) + self.hid_s_byte)
        if self.kgc.fast_cal:  # 快速计算
            P = self.kgc.k_AP2Ps_list[0][1]  # H_ID1*P2 + Ppub_s
            Q = self.kgc.Q1 + fast_kG(H_IDk, self.kgc.k_Q2_list)  # Q1 + H_IDk*Q2
            t = comb_pow(h_, self.kgc.gs_comb_list)
        else:
            H_ID1 = H(1, to_byte(ID_list[0]) + self.hid_s_byte)
            P, Q, t = P2 * H_ID1 + self.kgc.Ppub_s, self.kgc.Q1 + H_IDk * self.kgc.Q2, self.kgc.gs ** h_
        w_ = e(S1_, P) * e(Q, S2_).frobenius6() * t  # w'=e(S1', P)/e(Q, S2') * g**h'
        h2 = H(2, to_byte([M_, w_]))
        return h_ == h2


# 输入最大层数、测试次数
def test_HIBS(n, test_num):
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9_HIBS(IDA, -1, n, fast_cal=False)
    raw_ID_list = [IDA] + [IDA + str(i) for i in range(n - 1)]
    M_list = ['HIBS test' + str(i) for i in range(test_num)]

    print('\n----------------KGC生成用户（依次生成第2~%d层，测试%d次）----------------' % (n, test_num))
    kgc_gen_users1, kgc_gen_users2 = [], []
    time_1 = time.perf_counter()
    # 本文
    for k in range(2, n + 1):
        for _ in range(test_num):
            user1 = kgc.gen_user(raw_ID_list[:k])
        kgc_gen_users1.append(user1)
    time_2 = time.perf_counter()
    # 对照组
    for k in range(2, n + 1):
        for _ in range(test_num):
            user2 = kgc.gen_user(raw_ID_list[:k])  # gen_user1
        kgc_gen_users2.append(user2)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------用户生成用户（依次生成第3~%d层，测试%d次）----------------' % (n, test_num))
    user_gen_users1, user_gen_users2 = [kgc_gen_users1[0]], [kgc_gen_users2[0]]  # 第2层用户作为初始节点
    time_1 = time.perf_counter()
    # 本文
    for k in range(3, n + 1):
        for _ in range(test_num):
            user_next1 = user_gen_users1[-1].gen_user(raw_ID_list[:k])
        user_gen_users1.append(user_next1)
    time_2 = time.perf_counter()
    # 对照组
    for k in range(3, n + 1):
        for _ in range(test_num):
            user_next2 = user_gen_users2[-1].gen_user(raw_ID_list[:k])  # gen_user1
        user_gen_users2.append(user_next2)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------签名（第2~%d层依次，测试%d次）----------------' % (n, test_num))
    sig_list1, sig_list2 = [], []
    if kgc.fast_cal:
        for user1, user2 in zip(user_gen_users1, user_gen_users2):
            user1.pre_cal()
            user2.pre_cal()
    time_1 = time.perf_counter()
    # 本文
    for user in user_gen_users1:
        for i in range(test_num):
            sig_list1.append(user.sign(M_list[i]))
    time_2 = time.perf_counter()
    # 对照组
    for user in user_gen_users2:
        for i in range(test_num):
            sig_list2.append(user.sign(M_list[i]))  # sign1
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))

    print('\n----------------验签（第2~%d层依次，测试%d次）----------------' % (n, test_num))
    user1, user2 = user_gen_users1[-1], user_gen_users2[-1]
    time_1 = time.perf_counter()
    # 本文
    for k in range(2, n + 1):
        for i in range(test_num):
            assert user1.verify(raw_ID_list[:k], M_list[i], sig_list1.pop(0))
    time_2 = time.perf_counter()
    # 对照组
    for k in range(2, n + 1):
        for i in range(test_num):
            assert user2.verify(raw_ID_list[:k], M_list[i], sig_list2.pop(0))  # verify1
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('本文\t\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('对照组\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))


# 比较基础运算耗时
def test3(test_num):
    rs = [randrange(1, N) for _ in range(test_num)]
    G1_list, G2_list = [], []
    time_1 = time.perf_counter()
    for i in range(test_num):
        G1_list.append(P1 * rs[i])
    time_2 = time.perf_counter()
    for i in range(test_num):
        G2_list.append(P2 * rs[i])
    time_3 = time.perf_counter()
    for i in range(test_num):
        inv = mod_inv(rs[i], N)
    time_4 = time.perf_counter()
    for i in range(test_num):
        h = H(2, to_byte(rs[i]))
    time_5 = time.perf_counter()
    time_relative = time_2 - time_1
    print('G1标量乘\t耗时%.2f ms \t相对耗时%.2f' % ((time_2 - time_1) * 1000 / test_num, (time_2 - time_1) / time_relative))
    print('G2标量乘\t耗时%.2f ms \t相对耗时%.2f' % ((time_3 - time_2) * 1000 / test_num, (time_3 - time_2) / time_relative))
    print('Fp inv\t耗时%.2f ms \t相对耗时%.2f' % ((time_4 - time_3) * 1000 / test_num, (time_4 - time_3) / time_relative))
    print('Hash\t耗时%.2f ms \t相对耗时%.2f' % ((time_5 - time_4) * 1000 / test_num, (time_5 - time_4) / time_relative))


# ————————————————————————————————————论文—基于国密算法SM9的撤销加密方案—实验代码————————————————————————————————————
# 文献[1]：赖建昌, 黄欣沂, 何德彪, 等. 基于SM9的撤销加密方案[J]. 软件学报, 2024, 35(12): 5609-5620.
from math import factorial  # 阶乘
def comb_num(n, k):  # 计算组合数 C(n, k)
    return factorial(n) // (factorial(k) * factorial(n - k))


def cal_t_list(h_list, h_pow_list):  # 计算(Π(x+hi))/(x+h) = x^n-1 + t_0·x^n-2 +...+ t_n-3·x + t_n-2 + z/(x+h)的各项ti和z值
    # n = len(h_list)
    # z_list, a_list = [0 for _ in range(n)], [hi - h_pow_list[0] for hi in h_list]  # 初始化zi为全0，ai=hi-h
    # for i in range(n):  # 令y=x+h，原式 = (Π(y+ai))/y = y^n-1 + z_0·y^n-2 + ... + z_n-3·y + z_n-2 + z_n-1/y，计算各项zi值
    #     cal_z_list(a_list[i], 0, a_list[i + 1:], z_list)
    z_list = cal_z_list2([hi - h_pow_list[0] for hi in h_list])
    t_list, n = [], len(h_list) - 1
    for i in range(n):
        ti = z_list[i] + comb_num(n, i + 1) * h_pow_list[i]
        for j in range(i):
            ti += z_list[j] * comb_num(n-1-j, i-j) * h_pow_list[i-j-1]
        t_list.append(ti % N)
    return t_list, z_list[n]


class SM9_REVOKE(SM9):
    def __init__(self, sm9, ke, m):  # ke是加密私钥，m是撤销人数上限
        self.ID, self.ID_byte, self.Ppub_e, self.hid_e_byte = sm9.ID, sm9.ID_byte, sm9.Ppub_e, sm9.hid_e_byte
        self.de_a_list, self.k_Pe_list, self.ge_comb_list = sm9.de_a_list, sm9.k_Pe_list, sm9.ge_comb_list
        self.Ppub_list, alpha_i, self.h_pow_list, h_pow_i = [P1], ke, [], H(1, self.ID_byte + self.hid_e_byte)
        beta, gamma = randrange(1, N), randrange(1, N)  # 文献[1]参数
        self.r_ai_P1_list, self.r_ai_P2_list = [fast_kG(gamma, _kP1)], [fast_kG(gamma, _kP2)]  # 文献[1]参数
        for i in range(m):
            self.Ppub_list.append(fast_kG(alpha_i, _kP1))
            gama_alpha_i = gamma * alpha_i % N
            self.r_ai_P1_list.append(fast_kG(gama_alpha_i, _kP1))
            self.r_ai_P2_list.append(fast_kG(gama_alpha_i, _kP2))
            self.h_pow_list.append(h_pow_i)
            alpha_i, h_pow_i = alpha_i * ke % N, h_pow_i * self.h_pow_list[0] % N
        self.v_comb_list = get_comb_list(self.ge_pow(beta))  # 文献[1]参数
        t1_inv = mod_inv(self.h_pow_list[0] + ke, N)
        self.de_2 = fast_kG(ke * (beta + t1_inv) % N, _kP1)
        self.de_2_2 = fast_kG(ke * (beta + gamma * t1_inv) % N, _kP1)  # 安全证明版本，加γ
        self.de2 = fast_kG((beta + gamma * t1_inv) % N, _kP2)  # 文献[1]参数
        self.de2_a_list = get_a_list(self.de2)  # 文献[1]参数

    # 文献[1]
    def revoke_enc1(self, ID_list, klen=KEY_LEN):
        R = [to_byte(ID) for ID in ID_list]
        k = randrange(1, N)
        w = comb_pow(k, self.v_comb_list)
        C1 = fast_kG(k, self.k_Pe_list)
        h_list = [H(1, ID + self.hid_e_byte) for ID in R]
        C2 = accumulator(self.r_ai_P1_list, h_list) * k
        tao = h_list[0]
        for h in h_list[1:]:
            tao = tao * h % N
        K = KDF(to_byte([C1, C2, w, tao]), klen)
        return K, C1, C2

    def revoke_dec1(self, ID_list, C1, C2, klen=KEY_LEN, fast_e=False):
        R, n_1 = [to_byte(ID) for ID in ID_list], len(ID_list) - 1
        h_list = [H(1, ID + self.hid_e_byte) for ID in R]
        t_list, z = cal_t_list(h_list, self.h_pow_list)
        Q, tao_, z_inv = self.r_ai_P2_list[n_1], h_list[-1], mod_inv(z, N)
        for i in range(n_1):
            Q = Q + self.r_ai_P2_list[n_1 - 1 - i] * (t_list[i] % N)
            tao_ = tao_ * h_list[i] % N
        if fast_e:
            w_ = e(C1, self.de2 + Q * z_inv) * self.e_de(C2 * (N - z_inv))
        else:
            w_ = e_fast(C1, self.de2_a_list) * (self.e_de(C2) / e(C1, Q)) ** (N - z_inv)
        K_ = KDF(to_byte([C1, C2, w_, tao_]), klen)
        return K_

    # 本文
    def revoke_enc(self, ID_list, klen=KEY_LEN, add_gama=False):
        R = [to_byte(ID) for ID in ID_list]
        r = randrange(1, N)
        w = comb_pow(r, self.v_comb_list)
        C1 = fast_kG(r, _kP2)
        h_list = [H(1, ID + self.hid_e_byte) for ID in R]
        C2 = accumulator(self.r_ai_P1_list if add_gama else self.Ppub_list, h_list) * r
        K = KDF(to_byte([C1, C2, w, R]), klen)
        return K, C1, C2

    def revoke_dec(self, ID_list, C1, C2, klen=KEY_LEN, add_gama=False):
        R, n = [to_byte(ID) for ID in ID_list], len(ID_list)
        h_list = [H(1, ID + self.hid_e_byte) for ID in R]
        t_list, z = cal_t_list(h_list, self.h_pow_list)
        Ppub_list, de_2 = (self.r_ai_P1_list, self.de_2_2) if add_gama else (self.Ppub_list, self.de_2)
        Q, z_inv = Ppub_list[n], mod_inv(z, N)
        for i in range(n - 1):
            Q = Q + Ppub_list[n - 1 - i] * (t_list[i] % N)
        w_ = e(de_2 + Q * z_inv, C1) * self.e_de(C2 * (N - z_inv))
        K_ = KDF(to_byte([C1, C2, w_, R]), klen)
        return K_


# 输入撤销用户数量列表、测试次数列表
def test_revoke(n_list, test_num_list):
    IDA = 'ALICE123@YAHOO.COM'
    IDB = 'ALICE123@YAHOO.COM0'
    kgc = SM9(ke=-1)
    max_n = max(n_list)
    sm9_A = SM9_REVOKE(kgc.KGC_gen_user(IDA), kgc.ke, max_n)  # 撤销加密对象
    sm9_B = SM9_BROADCAST(kgc.KGC_gen_user(IDB), kgc.ke, max_n)  # 广播加密对象
    raw_ID_list = [IDA + str(i) for i in range(max_n)]
    for n, test_num in zip(n_list, test_num_list):
        print('\n----------------可撤销加密（%d个撤销/广播用户，测试%d次）----------------' % (n, test_num))
        res_list1, res_list2, res_list3 = [], [], []
        ID_list = raw_ID_list[:n]
        # sm9_A.pre_cal(ID_list)
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res_list1.append(sm9_A.revoke_enc1(ID_list))
        time_2 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res_list2.append(sm9_A.revoke_enc(ID_list))
        time_3 = time.perf_counter()
        # 广播加密
        for i in range(test_num):
            res_list3.append(sm9_B.broad_enc(ID_list))
        time_4 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
        print('本文\t\t\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
        print('广播加密\t\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, time_relative / (time_4 - time_3)))

        print('\n---------------消息解密（%d个撤销/广播用户，测试%d次）--------------' % (n, test_num))
        res1, res2, res3, res4 = [], [], [], []
        time_1 = time.perf_counter()
        # 文献[1]
        for i in range(test_num):
            res1.append(sm9_A.revoke_dec1(ID_list, *res_list1[i][1:]) == res_list1[i][0])
        time_2 = time.perf_counter()
        # 文献[1]优化
        for i in range(test_num):
            res2.append(sm9_A.revoke_dec1(ID_list, *res_list1[i][1:], fast_e=True) == res_list1[i][0])
        time_3 = time.perf_counter()
        # 本文
        for i in range(test_num):
            res3.append(sm9_A.revoke_dec(ID_list, *res_list2[i][1:]) == res_list2[i][0])
        time_4 = time.perf_counter()
        # 广播加密
        for i in range(test_num):
            res4.append(sm9_B.broad_dec(ID_list, *res_list3[i][1:]) == res_list3[i][0])
        time_5 = time.perf_counter()
        time_relative = time_2 - time_1
        print('文献[1]\t\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
        print('文献[1]优化\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
        print('本文\t\t\t耗时%.2f ms \t相对速率%.2f' % ((time_4 - time_3) * 1000 / test_num, time_relative / (time_4 - time_3)))
        print('广播加密\t\t耗时%.2f ms \t相对速率%.2f' % ((time_5 - time_4) * 1000 / test_num, time_relative / (time_5 - time_4)))
        assert all(res1) and all(res2) and all(res3) and all(res4)


# ————————————————————————————————————论文—基于基域表示的SM9高次扩域运算优化—实验代码————————————————————————————————————
def test_new_FQ12(test_num):
    from hggm.SM9 import FQ12 as new_FQ12, e as e_new, P2 as P2_new
    IDA = 'ALICE123@YAHOO.COM'
    kgc = SM9(ke=-1)
    sm9 = kgc.KGC_gen_user(IDA)
    g_list = [sm9.ge, sm9.ge_pow(randrange(1, N))] + [None] * test_num  # GT上的元素
    g_list2 = [new_FQ12(x.get_fp_list()[::-1]) for x in g_list[:2]] + [None] * test_num

    def test_memory():  # 分析内存占用峰值
        import tracemalloc
        a, c, b, d, n = g_list[1], g_list[0], g_list2[1], g_list2[0], N - 1
        print('---------------内存占用峰值--------------')
        print('运算\t\t塔式扩张\t基域表示\t降幅')
        tracemalloc.start()
        tracemalloc.clear_traces()
        a * c
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b * d
        peak2 = tracemalloc.get_traced_memory()[1]
        print('FQ12乘法\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.sqr()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.sqr()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('FQ12平方\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.GT_sqr()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.GT_sqr()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('GT平方\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.inv()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.inv()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('FQ12求逆\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.frobenius()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.frobenius()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('frobenius\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.frobenius2()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.frobenius2()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('frobenius2\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.frobenius3()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.frobenius3()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('frobenius3\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a.frobenius6()
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b.frobenius6()
        peak2 = tracemalloc.get_traced_memory()[1]
        print('frobenius6\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        a ** n
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        b ** n
        peak2 = tracemalloc.get_traced_memory()[1]
        print('GT上的幂\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.clear_traces()
        e(P1, P2)
        peak1 = tracemalloc.get_traced_memory()[1]
        tracemalloc.clear_traces()
        e_new(P1, P2_new)
        peak2 = tracemalloc.get_traced_memory()[1]
        print('双线性对\t\t%d B\t%d B\t%.2f%%' % (peak1, peak2, ((peak1 - peak2) / peak1 * 100)))
        tracemalloc.stop()
    test_memory()

    print('\n---------------FQ12乘法（测试%d次）--------------' % (test_num))
    time_1 = time.perf_counter()
    for i in range(test_num):
        g_list[i+2] = g_list[1] * g_list[i+1]
    time_2 = time.perf_counter()
    for i in range(test_num):
        g_list2[i+2] = g_list2[1] * g_list2[i+1]
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    g_list, g_list2 = g_list[2:], g_list2[2:]  # 生成的g_list, g_list2用作后续测试的输入
    assert all(x == y for x, y in zip(g_list, g_list2))

    print('\n---------------FQ12平方（测试%d次）--------------' % (test_num))
    sqr1, sqr2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        sqr1[i] = x.sqr()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        sqr2[i] = y.sqr()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(sqr1, sqr2))

    print('\n---------------GT平方（测试%d次）--------------' % (test_num))
    GT_sqr1, GT_sqr2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        GT_sqr1[i] = x.GT_sqr()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        GT_sqr2[i] = y.GT_sqr()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y == w for w, x, y in zip(sqr2, GT_sqr1, GT_sqr2))

    print('\n---------------FQ12求逆（测试%d次）--------------' % (test_num))
    inv1, inv2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        inv1[i] = x.inv()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        inv2[i] = y.inv()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(inv1, inv2))

    print('\n---------------frobenius（测试%d次）--------------' % (test_num))
    frobenius_1, frobenius_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        frobenius_1[i] = x.frobenius()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        frobenius_2[i] = y.frobenius()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(frobenius_1, frobenius_2))

    print('\n---------------frobenius2（测试%d次）--------------' % (test_num))
    frobenius2_1, frobenius2_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        frobenius2_1[i] = x.frobenius2()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        frobenius2_2[i] = y.frobenius2()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us  \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(frobenius2_1, frobenius2_2))

    print('\n---------------frobenius3（测试%d次）--------------' % (test_num))
    frobenius3_1, frobenius3_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        frobenius3_1[i] = x.frobenius3()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        frobenius3_2[i] = y.frobenius3()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us  \t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(frobenius3_1, frobenius3_2))

    print('\n---------------frobenius6（测试%d次）--------------' % (test_num))
    frobenius6_1, frobenius6_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, x in enumerate(g_list):
        frobenius6_1[i] = x.frobenius6()
    time_2 = time.perf_counter()
    for i, y in enumerate(g_list2):
        frobenius6_2[i] = y.frobenius6()
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f us \t\t相对速率%.2f' % ((time_2 - time_1) * 1000000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f us \t\t相对速率%.2f' % ((time_3 - time_2) * 1000000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(frobenius6_1, frobenius6_2))

    test_num //= 100
    n_list = [randrange(1, N) for _ in range(test_num)]
    print('\n---------------GT的幂（测试%d次）--------------' % (test_num))
    pow_1, pow_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, n in enumerate(n_list):
        pow_1[i] = g_list[i] ** n
    time_2 = time.perf_counter()
    for i, n in enumerate(n_list):
        pow_2[i] = g_list2[i] ** n
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f ms \t\t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(pow_1, pow_2))

    print('\n---------------双线性对（测试%d次）--------------' % (test_num))
    G1_list = [fast_kG(n, _kP1) for n in n_list]
    e_1, e_2 = [None] * test_num, [None] * test_num
    time_1 = time.perf_counter()
    for i, p1 in enumerate(G1_list):
        e_1[i] = e(G1_list[i], P2)
    time_2 = time.perf_counter()
    for i, p1 in enumerate(G1_list):
        e_2[i] = e_new(G1_list[i], P2_new)
    time_3 = time.perf_counter()
    time_relative = time_2 - time_1
    print('塔式扩张\t耗时%.2f ms \t相对速率%.2f' % ((time_2 - time_1) * 1000 / test_num, time_relative / (time_2 - time_1)))
    print('基域表示\t耗时%.2f ms \t相对速率%.2f' % ((time_3 - time_2) * 1000 / test_num, time_relative / (time_3 - time_2)))
    assert all(x == y for x, y in zip(e_1, e_2))
    # a, b=frobenius6_1[0].get_fp_list()[::-1], frobenius6_2[0].coeffs
    # print([i for i in range(12) if a[i]!=b[i]])


if __name__ == "__main__":
    # test_homo(500, [2, 16, 256], [100, 100, 20])  # 同态加密
    # test_ring([4, 16, 64, 256, 1024], [10] * 5)  # 环签名
    # test_ring2([4, 16, 64, 256, 1024], [2] * 5)  # 环签名2
    # test_accuring([4, 16, 64, 256, 1024], [30] * 5)  # 可追踪环签名
    # test_signenc(100)  # 签密
    # test_revoke([4, 8, 16, 32, 64], [5] * 5)  # 可撤销加密
    # test_GTDLP([42, 44, 46], [20, 10, 3])  # 群GT上的DLP
    # test_AHE_GTDLP([46], [20])  # 采用不同DLP算法的AHE
    # test_new_FQ12(1000)  # 基域表示
    # test_ringsignenc([4, 16, 64, 256, 1024], [100, 100, 100, 100, 20])  # 环签密

    test_broadcast([4, 16, 64, 256, 1024], [10, 10, 10, 2, 2])  # 广播加密
    # test_HIBE(16, 5)  # 分层标识加密
    # test_HIBS(16, 2)  # 分层标识签名
    # test3(1000)
    # sm9_prof_test()
